Problems

You have a file with 100 billion URLS, find first unique URL.
Design a data structure for following operations in O(1) time.:
insert
remove (FIFO)
find MODE
Design an LRU cache, where you remove an element not only by time lapsed since last used but also by a cost associated with each element. F(t, c) is a method to find weight for each element. Where c is cost and t is time since last used.
Implement DFS

After I implemented this, I was told to implement it without recursion. He told me to write pseudo code. I wrote it using stacks.
Given a matrix (0,0 is to the botto9m left like co-ordinate system)of 0s and 1s and two co-ordinates find if there is a path between them, Also you can only travel via 1s and you can only go up or right.

Answer: Backtracking algorithm
given K sorted arrays merge them

Answer: Told him how to do using merge of merge sort. He wanted me to do another approach I googled later you can use min heap for it.

Given an array of integers find the element for which the sum of left = sum of right. example -1 100 1 98 1 should return index of 1 i.e 2

Answer: First told him about Brute Force approach and then told him if we can iterate once and get the total sum

int findIndex(A){

int sum =0;
   for(int i =0;i<A.lenght;i++)
   {
       sum+= A[i];
   }
   
   int lSum=0;
   for(int i=0;i<A.length;i++)
   {
       int rsum = sum - lsum-A[i];
       
       if(lsum==rsum)
       return i;
       
       lsum += A[i];
       
   }
   
   return -1;

}

The closest common ancestor in a tree forest.

class Node {
    Node* parent; // == null for root of tree
    Node* left;
    Node* right;
}

Node* tree_forest[]; // array of pointers which points to roots of each tree respectively

Node* closest_common_ancestor(Node* n1, Node* n2) {
    // your solution
}

Example:

|    a     |   j
|   / \    |  /
|  b   c   | h
| /   / \  |
|d   e   f |

for e and d CCA is a
for e and f CCA is c
for e and c CCA is c
for h and d CCA is null

Constrains: O(1) additional memory

int findIndex(A){

int sum =0;
   for(int i =0;i<A.lenght;i++)
   {
       sum+= A[i];
   }
   
   int lSum=0;
   for(int i=0;i<A.length;i++)
   {
       int rsum = sum - lsum-A[i];
       
       if(lsum==rsum)
       return i;
       
       lsum += A[i];
       
   }
   
   return -1;

}

The closest common ancestor in a tree forest.

class Node {
    Node* parent; // == null for root of tree
    Node* left;
    Node* right;
}

Node* tree_forest[]; // array of pointers which points to roots of each tree respectively

Node* closest_common_ancestor(Node* n1, Node* n2) {
    // your solution
}

Example:

|    a     |   j
|   / \    |  /
|  b   c   | h
| /   / \  |
|d   e   f |

for e and d CCA is a
for e and f CCA is c
for e and c CCA is c
for h and d CCA is null

Constrains: O(1) additional memory

This question was asked in the chat, just adding here with the solution. I don't know for which company it is.

Replace wild cards with all possible combinations of zeros and ones using recursion.

Input String: 0?1?
Output: 0010, 0011, 0110, 0111

This is my solution using recursion:

import java.util.*;

public class ReplaceWildcardsRec {
	public static List<String> expandString(String s, int i) {
		List<String> l = new ArrayList<String>();
		if(i>s.length()-1) {
			l.add("");
			return l;
		}
		for(String expanded: expandString(s,i+1)) {
			if(s.charAt(i)=='?') {
				l.add('0'+expanded);
				l.add('1'+expanded);
			}
			else {
				l.add(s.charAt(i)+expanded);
			}
		}
		return l;
	}
	public static void main(String[] args) {
		List<String> l =  new ArrayList<String>();
		String s = "1111?";
		l = expandString(s,0);
		System.out.println(l);
	}
}

implement database structure in Java (that would be multithreaded)

I was at a job interview and the intreviewer gave me a task: I have an object called DBconn. that Object has 4 methods:

• connect(Params)

• query(String)

• update (String)

• disconnect()

My mission was to implement that Database object (DBconn) in a singelton pattern - meaning the first person who create this object will get a new instance of it and from there one - every person will get that instance of the databse (not to create a new instance for every user - but share the same object).

I first tried to us the standard way of singelton where I create a DBconn object in the first time that a user called it - and return the instance from there on. The problem was that the connect method should only run for the first time (meaning user1 connect, and then user 2 also connect - is not valid) and if I return the databse every user that want to harm to system can conncect or diconnect as he please.

So i decided to return the singelton class (instead of the database object), and do the "connect" only for the first user. But then I encounter a diffrente problem: the query and update methods of the DBconn should work in multythread way (meaning they are synchornized - according to DBconn implemetion). But if I write them in a synchronized java method that will force the program to excute each of them speratly (because of the "synchronized" saved word) and that will ignore the beauty multythreaded way that "update" and "query" work.

So he gave me a homework task (which ovcourse inclueded using the internet and counslting) - to try and solve this problem by writing it in java.

this is what I did so far (I also tried to implememts a very raw database which saves persons data) but I still don't know how to make the update and query to: 1. work in a muiltythread way. 2. work in a muiltythread way in the singelton class as well

Thanks for all of you who trying to help:

SingeltonDB:

public class SingeltonDB {
	private static DBconnImpl db = null;
	private static SingeltonDB singalDb = null;

	private SingeltonDB(String username, String password) {
		db = new DBconnImpl();
	}

	public static boolean isOpen() {
		return (db != null);
	}

	public synchronized static SingeltonDB getInstance(String username,
			String password) throws Exception {
		if (db != null) {
		} else {
			System.out.println("The database is now open");
			singalDb = new SingeltonDB(username, password);
		}
		db.connect(username, password);
		System.out.println("The database was connected");
		return singalDb;
	}

	public synchronized static SingeltonDB getInstance() throws Exception {
		if (db == null) {
			throw (new Exception("The database is not open"));
		}

		return singalDb;
	}

	public void create(String tableName) throws Exception {
		db.create(tableName);
	}

	public User query(String tableName, int rowID) throws Exception {
		if (db == null) {
			System.out.println("Error: the database is not open");
			return null;
		}
		return (db.query(tableName, rowID));
	}

	public void update(String tableName, User user) throws Exception {
		if (db == null) {
			System.out.println("Error: the database is not open");
			return;
		}
		db.update(tableName, user);
	}

}

DBconnImpl:

import java.util.*;

public class DBconnImpl {

	private Map<String, Table> tables;
	private boolean connected;

	private String username;
	private String password;

	public DBconnImpl() {
		tables = new HashMap<>();
		this.username = "MyAccount";
		this.password = "123";
		connected = false;
	}

	public boolean connect(String username, String password) throws Exception {
		if (connected) {
			throw (new Exception("Error: The database is already opened."));
		}
		if (!this.username.equals(username) || !this.password.equals(password)) {
			System.out.println("wrong username or password.");
			return false;
		}
		connected = true;
		return true;
	}

	public void create(String tableName) throws Exception {
		if (!connected) {
			throw (new Exception("Error: The database is not opened."));
		}
		tables.put(tableName, new Table(tableName));
	}

	public User query(String tableName, int rowID) throws Exception {
		if (!connected) {
			throw (new Exception("Error: The database is not opened."));
		}
		return (tables.get(tableName).query(rowID));
	}

	public void update(String tableName, User user) throws Exception {
		if (!connected) {
			throw (new Exception("Error: The database is not opened."));
		}
		tables.get(tableName).update(user);
	}

	public boolean disconnect() throws Exception {
		if (!connected) {
			throw (new Exception("Error: The database is not opened."));
		}
		connected = false;
		return true;
	}

}

Table

import java.util.*;

public class Table {

	private Map<Integer, User> table;

	public Table(String tableName) {
		table = new HashMap<>();
	}

	public User query(int id) throws Exception {
		return table.get(id);
	}

	public void update(User user) throws Exception {
		table.put(user.getId(), user);
		System.out.println("The user " + user.getName()
				+ " was successfully entered in the with ID number "
				+ user.getId() + ".");

	}

}

User

public class User {
	private String name;
	private int id;
	private int age;

	public User(int id, String name, int age) {
		this.name = name;
		this.age = age;
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public int getAge() {
		return age;
	}

	public int getId() {
		return id;
	}

	@Override
	public String toString() {
		return ("(" + name + " , " + age + ")");
	}
}

UserContorller

public class UserContorller {
	SingeltonDB db;

	public UserContorller(String user, String pass) throws Exception {
		if (!SingeltonDB.isOpen()) {
			db = SingeltonDB.getInstance(user, pass);

		} else {
			System.out.println("dataBase already opened");
		}
	}

	public UserContorller() throws Exception {
		if (SingeltonDB.isOpen()) {
			db = SingeltonDB.getInstance();
		} else {
			System.out.println("dataBase not opened");
		}
	}

	public void createTable(String table) throws Exception {
		db.create(table);
	}

	public void saveUser(String table, int id, String name, int age)
			throws Exception {
		db.update(table, new User(id, name, age));
	}

	public User getUser(String table, int id) throws Exception {
		return db.query(table, id);
	}

}

Main

public class Main {
	public static void main(String[] args) throws Exception {

		UserContorller uc1 = new UserContorller("MyAccount", "123");
		UserContorller uc2 = new UserContorller();
		UserContorller uc3 = new UserContorller();

		uc1.createTable("table1");
		uc2.saveUser("table1", 1, "David", 10);
		System.out.println(uc3.getUser("table1", 1));

	}
}

Reverse last 5 nodes of linkedlist. Please let me know if there is any better way.
E.g.
Input: 1,2,3,4,5,6,7
Output: 1,2,7,6,5,4,3

package com.acct;

public class SinglyLinkedListReverseLast5 {

	public static void main(String[] args) {
		Node n7 = new Node(7, null);
		Node n6 = new Node(6, n7);
		Node n5 = new Node(5, n6);
		Node n4 = new Node(4, n5);
		Node n3 = new Node(3, n4);
		Node n2 = new Node(2, n3);
		Node n1 = new Node(1, n2);
		int numberOfNodestoReverse  = 5;
		System.out.println(n1.toString());

		reverse(getNthElement(n1, numberOfNodestoReverse+1));
		System.out.println(n1.toString());
	}

	public static Node getNthElement(Node head, int n) {
		Node f_ptr = head;
		Node s_ptr = head;

		for (; n > 0; n--) {
			f_ptr = f_ptr.next;
		}

		while (f_ptr != null) {
			f_ptr = f_ptr.next;
			s_ptr = s_ptr.next;
		}
		System.out.println(s_ptr.toString());

		return s_ptr;

	}

	public static void reverse(Node head) {
		Node current = null;
		Node next;
		Node first = head;
		head = head.next;
		while (head != null) {
			next = head.next;
			head.next = current;
			current = head;
			head = next;
		}
		first.next = current;
	}
}

class Node {
	int value;
	Node next;

	Node(int value, Node next) {
		this.value = value;
		this.next = next;
	}

	public String toString() {
		String result = value + " ";
		if (next != null) {
			result += next.toString();
		}
		return result;
	}
}

You have just earned $500 voucher to spend at any restaurant. However,
since you are a programmer and a foodie you want to maximize how you
allocate your money.

Attached is CSV that has a list of:

-Beverages
-Appetizers
-Entrees
-Desserts
-Restaurants

The CSV file looks something like
Beverage Name,Beverage Cost,Beverage Value,Appetizer Name,Appetizer Cost,Appetizer Value,Entrée Name,Entrée Cost,Entrée Value,Desert Name,Desert Cost,Desert Value,Restaurant Name,Restaurant Drink Cost,Restaurant Value
7up, $92.00 ,32,Fresh Rolls, $82.00 ,30,Fried Rice, $78.00 ,29,Vanilla Ice Cream, $76.00 ,13,Applebee's, $43.00 ,19
Sprite, $89.00 ,24,Spring Rolls, $54.00 ,18,PB & J, $49.00 ,29,chocolate cake, $50.00 ,25,Arby's, $26.00 ,5

Next to each item there is a cost and a perceived value.

Your job is to construct a meal under your budget of $500 that includes:

1 Beverage
3 Appetizers
2 Entrees
1 Dessert
1 Flex Option (This can be an Appetizer, Entree, or Desert)
1 Restaurant

1. Please list the 25 Combinations with the highest perceived value
given your budget
2. Please list the 25 Combinations with the lowest perceived value
given your budget.

Make sure your program assumes that the number of items in each
category is N

The problem I am having is using the knapsack algorithm in this case, especially with item constraints. The problem seems to be poorly written.

public static void main(String[] args) throws IOException {
        File file = new File("Menu.csv");

        List<String> lines = Files.readAllLines(file.toPath(),
                StandardCharsets.UTF_8);
        List<Beverage> beverages = new ArrayList<>();
        List<Appetizer> appetizers = new ArrayList<>();
        List<Entree> entrees = new ArrayList<>();
        List<Dessert> desserts = new ArrayList<>();
        List<RestaurantDrink> restaurantDrinks = new ArrayList<>();
        boolean firstLine = true;
        for (String line : lines) {
            if (firstLine)
            {
                firstLine = false;
                continue; //don't care about first line
            }
            String[] array = line.split(",");
            int j = 0;
            Beverage b = new Beverage();
            Appetizer app = new Appetizer();
            Entree e = new Entree();
            Dessert d = new Dessert();
            RestaurantDrink rd = new RestaurantDrink();

            for (String a : array) {
               switch (j)
               {
                   case 0:
                       if (!a.equals("")) //nothing
                       {
                           b.name = a;
                           
                       }
                       break;
                   case 1:
                       if (!a.equals("")) //nothing
                       {
                           b.cost = Double.parseDouble(a.replace("$", ""));
                           
                       }

                       break;
                   case 2:
                       if (!a.equals("")) //nothing
                       {
                           b.perceivedValue = Integer.parseInt(a);
                         
                           beverages.add(b);
                       }
                       break;
                   case 3:
                       app.name = a;
                      
                       break;
                   case 4:
                       app.cost = Double.parseDouble(a.replace("$", ""));
                      
                       break;
                   case 5:
                       app.perceivedValue = Integer.parseInt(a);
                      
                       appetizers.add(app);
                       break;
                   case 6:
                       e.name = a;
                       
                       break;
                   case 7:
                       e.cost = Double.parseDouble(a.replace("$", ""));
                      
                       break;
                   case 8:
                       e.perceivedValue = Integer.parseInt(a);
                      
                       entrees.add(e);
                       break;
                   case 9:
                       d.name = a;
                      
                       break;
                   case 10:
                       if (a.equals("")) //free dessert
                       {
                           d.cost = 0.00;
                       } else {
                           d.cost = Double.parseDouble(a.replace("$", ""));
                       }
                      
                       break;
                   case 11:
                       if (a.equals("")) //free dessert
                       {
                           d.perceivedValue = 0;
                       } else {
                           d.perceivedValue = Integer.parseInt(a);
                       }

                       desserts.add(d);
                       break;
                   case 12:
                       rd.name = a;
                       break;
                   case 13:
                       if (a.equals("")) //free restaurant drink
                       {
                           rd.cost = 0.00;
                       } else {
                           rd.cost = Double.parseDouble(a.replace("$", ""));
                       }

                       break;
                   case 14:
                       if (a.equals("")) //free dessert
                       {
                           rd.perceivedValue = 0;
                       } else {
                           rd.perceivedValue = Integer.parseInt(a);
                       }

                       restaurantDrinks.add(rd);
                       break;
               }
                j++;
            }
            j = 0;

        }
}

is all I got. I'm just having trouble with the knapsack portion.

Jumper Game: A NxN grid which contains either of 0-empty, 1 - player 1, 2 - player 2. Given a position in the grid, find the longest jump path. For jump path, you can jump only diagonally, you can jump on opponent cell and also the landing cell should be empty. No opponent cell can be jumped more than once. Write a function which takes grid and a specific position in the grid, and returns the longest possible number of jumps in the grid. For Example:
if grid = {
			{ 0,0,0,0,0,0 },
			{ 0,1,0,0,0,0 },
			{ 2,0,2,0,2,0 },
			{ 0,0,0,0,0,0 },
			{ 0,0,0,0,0,0 },
			{ 0,0,0,0,0,0 },				
	};
Answer should be 2 - (1,1) -> (3,3) -> (1,5)

You are given an mxn grid, where (0,0) refers top most left position and (m-1,n-1) the bottom most right. The grid is filled with ones. All positions in the grid that are blocked are filled with zeros. You are given this grid and are assured that there exists atleast one path from (0,0) to (m-1, n-1). Find the minimum distance of the path from (0,0) to (m-1, n-1) given that you are allowed to move only vertically, horizontally and diagonally

There are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit.
Design a data structure to represent the floor and door design.  A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.

int fun()
{
	/*write code here.*/
}
int main()
{
	int i=10;
	fun();
	printf("%d",i);
}

change the value of the i without changing code of the main function, assign 20 to i ?

Given a String s and a hashmap containing certain decodings for all the characters of alphabet. Find all possible passwords that can be generated by replacing decodings in the string s. 
Note that decodings of a charachter can only be single charachters
Eg: String s="abcde"
decodings given
a-{1,2,p,o,q}
b-{2,y}
c-{p}
d-{4,a,m,n}
e-{9,z,x}
h-{1}
'
'
'
x-{0}
y-{4,k,l}
z-{r,5}
So possible set passwords will be 
abcde,1bcde,2bcde,pbcde,obcde,qbcde,     //replace a with all possible decodings
a2cde,12cde,22cde,p2cde,o2cde,q2cde,aycde,1ycde,2ycde,pycde,oycde,qycde      //replace b will all possible decodings
a2pde,12pde,22pde,p2pde,o2pde,q2pde,aypde,1ypde,2ypde,pypde,oypde,qypde.....//replace c will all possible decodings

public abstract class Session{
	private Object objectId;
	//... other fields
	public abstract void processRequest(InputStream in);
}

public XmlSession implements Session{
	public void processRequest(InputStream in){
		System.out.println("XML RESPONSE");
		// DO STUFF TO XML RESPONSE
	}
}

public JSonSession implements Session{
	public void processRequest(InputStream in){
		System.out.println("JSON RESPONSE");
		// DO STUFF TO JSON RESPONSE
	}
}

public static void main(String args[]){
   Session session = new XmlSession();
   session.processRequest();

    Session session = ....;
    session.processRequest();
}

I would like to change my design in a way that I will not lose the Session object and I don't change the client code that instanciate the XmlSession.

Could it be useful the prototype pattern? If yes why?

what does this code do?

unsigned mystery(unsigned x) {
   unsigned i=0;
   while(x) {
     x=x&(x-1);
     i++;
   }
   return i;
}

write a program to return min value from an unsorted array of integers. How many assignment operations happen within the loop?

what does this code do?

unsigned mystery(unsigned x) {
  unsigned i=0;
  while(x) {
     x=x&(x-1);
     i++;
  }
  return i;
}

Whats the time complexity of this code?
When I told him its O(N^3), he told me to look carefully, its O(N^2),
I dont know why? Any idea?

for (int i = 0; i < n-2; ++i)
    {
    	//some code
        for (int j = i+1; j < n-1; ++j)
        {
        	//some code
        	for (int k = j+1; k < n; ++k)
        	{
        		//some code
        	}
        }

}

Implement a function to return top rated movies in the network of movies reachable from the current movie.

* eg.            A(Rating 1.2)
     *               /   \
     *            B(2.4)  C(3.6)
     *              \     /
     *                D(4.8)

In the above example, edges represent similarity and the number is rating.
* getMovieRecommendations(A,2) should return C and D (sorting order doesn't matter so it can also return D and C)
* getMovieRecommendations(A,4) should return A, B, C, D (it can also return these in any order eg: B,C,D,A)
* getMovieRecommendations(A,1) should return D. Note distance from A to D doesn't matter, return the highest rated.

import java.util.ArrayList;
import java.util.List;
 
public class Movie {
    private final int movieId;
    private final float rating;
    private List<Movie> similarMovies; // Similarity is bidirectional
 
    public Movie(int movieId, float rating) {
        this.movieId = movieId;
        this.rating = rating;
        similarMovies = new ArrayList<Movie>();
    }
 
    public int getId() {
        return movieId;
    }
 
    public float getRating() {
        return rating;
    }
 
    public void addSimilarMovie(Movie movie) {
        similarMovies.add(movie);
        movie.similarMovies.add(this);
    }
 
    public List<Movie> getSimilarMovies() {
        return similarMovies;
    }
 
     /*  *     
     *     @param movie
     *     @param numTopRatedSimilarMovies 
     *                      number of movies we want to return
     *     @return List of top rated similar movies
     */
    public static List<Movie> getMovieRecommendations(Movie movie, int numTopRatedSimilarMovies) {
        // Implement me
        return null;
    }
}

How would you implement this:

object["String for a security name"]["another string"] = another_object

Any feedback about my performance would be helpful.

I have my (unfinished) answer that I managed to code by the end of the interview. I also have my answer that I coded after the interview was over. Did I miss anything, or is there a simpler answer out there? I feel like I was pretty close, although I didn't finish, which feels pretty bad.

Palindrome question:
Is a string reversible?
Ignore illegal characters; ignore case. Only alphabetic characters are valid.

Here was my answer after ~45 mins:

/*
 * Compare both ends for equality, meeting in the middle
 */

public static boolean isReversible(String s) {
    
    char[] chars = s.toCharArray();
    int back = chars.length - 1;
    int front = 0;
    int middle = chars.length / 2;


    while (front < back) {
        char backChar = chars[back];
        char frontChar = chars[front];
        // check backChar as a alpha char
        while (backChar < ‘a’ || backChar > ‘z’) {
            back--;
            
            if (back < middle)
                return false;
            
            // Double check for multiple non-alpha chars
            middle--;
            backChar = chars[back];
        }
        
        // check frontChar as a alpha char
        while (frontChar < ‘a’ || backChar > ‘z’) {
            front++;
            
            if (front >= middle)
                return false;

            // Double check for multiple non-alphas
            middle++;

            frontChar = chars[front];
        }  

        // We know that frontChar and backChar are both alpha   
        // Check whether front and back are not past the middle
        

        if (frontChar != backChar)
            return false;
        
        front++;
        back--;

    }

    return true;      
}

Here was an answer that I came up with after the interview, which I believe is complete after manual testing:

/*
 * Compare both ends for equality, meeting in the middle
 */

public static boolean isReversible(String s) {
    s = s.toLowerCase();
    char[] chars = s.toCharArray();
    int back = chars.length - 1;
    int front = 0;


    while (front < back) {
        char backChar = chars[back];
        char frontChar = chars[front];
        // check backChar as an alpha char
        while (backChar < 'a' || backChar > 'z') {
            back--;
            
            if (back < front)
                return true;
            
            backChar = chars[back];
        }
        
        // check frontChar as an alpha char
        while (frontChar < 'a' || frontChar > 'z') {
            front++;
            
            if (front > back)
                return true;

            frontChar = chars[front];
        }

        if (frontChar != backChar)
            return false;

        front++;
        back--;

    }

    return true;      
}

Write a calculator program in a Java that evaluates expressions in a very simple integer expression language.   The program takes an input on the command line, computes the result, and prints it to the console.  For example:
 
% java calculator.Main “mult(2, 2)”
 
4
 
Few more examples:
 
Input

Output

add(1, 2)

3

add(1, mult(2, 3))

7

mult(add(2, 2), div(9, 3))

12

let(a, 5, add(a, a))

10

let(foo, 5, let(bar, mult(foo, 10), add(bar, foo)))

55

let(a, let(b, 10, add(b, b)), let(b, 20, add(a, b)))

40

An expression consists of:
·          Numbers: integers between Integer.MIN_VALUE and Integer.MAX_VALUE

·          Variables: strings of characters, where each character is one of a-z, A-Z

·          Arithmetic functions: add, sub, mult, div, each taking two arbitrary expressions as arguments.  In other words, each argument may be any of the expressions on this list.

·          A “let” operator for assigning values to variables:

let(<variable name>, <value>, <expression where variable is used>)

As with arithmetic functions,  the expression where the variable is used may be an arbitrary expression from this list.

Design a data structure which has following operations:

1. void add(e)
2. void delete(e)
3. boolean contains(e)
4. e getRandom()
5. e getMostRecent()

All operations should be preferably O(1)

You are given a mxn grid arr[][] and you stand at cell arr[p][q]. In 1 'move' you can either go up, down , left or right. Tell the probability that after taking 'k' moves, you are still inside the grid.

CODE:
(Can you point out any mistake)

#include <stdio.h>
#include <stdlib.h>


void traverse(int m, int n,int cur_x,int cur_y,int moves,int * in,int * tot)
{
	if(moves==0)
	*tot = *tot+1;
	if(moves==0 && !(cur_x>=m||cur_y>=n||cur_x<0||cur_y<0))
	*in = *in +1;
	
	traverse(m,n,cur_x,cur_y+1,moves-1,in,tot);
	traverse(m,n,cur_x+1,cur_y,moves-1,in,tot);
	traverse(m,n,cur_x,cur_y-1,moves-1,in,tot);
	traverse(m,n,cur_x-1,cur_y,moves-1,in,tot);
}

int main()
{
    int m = 5, n = 5;
    int in=0,tot=0;
    int k,p,q;
    scanf("%d%d%d",&k,&p,&q);
    traverse(m,n,p,q,k,&in,&tot);
    printf("%d/%d ",in,tot);
	return 0;
}

Given a binary tree where all the right nodes are leaf nodes, flip it upside down and turn it into a tree with left leaf nodes.

Keep in mind: ALL RIGHT NODES IN ORIGINAL TREE ARE LEAF NODE.

/* for example, turn these:
 *
 *        1                 1
 *       / \                 / \
 *      2   3            2   3
 *     / \
 *    4   5
 *   / \
 *  6   7
 *
 * into these:
 *
 *        1               1
 *       /               /
 *      2---3         2---3
 *     /
 *    4---5
 *   /
 *  6---7
 *
 * where 6 is the new root node for the left tree, and 2 for the right tree.
 * oriented correctly:
 *
 *     6                   2
 *    / \                   / \
 *   7   4              3   1
 *        / \
 *       5   2
 *            / \
 *          3   1
 */

Print a tree in Level Order with a newline after each depth

/**
 * Sample input:
 *
 *          1
 *         / \
 *        3   5
 *       / \   \
 *      2   4   7
 *     /     \
 *    9       8
 *
 * Expected output:
 *    1
 *    3 5
 *    2 4 7
 *    9 8
 *    ==========
 */

struct node
{
     int data;
     struct node* left;
     struct node* right;
};

void Postorder(struct node* root,struct node** leaf)
{
     if (root == NULL)
        return;
	
	if(root->data%2==0)
	*leaf->left=root;		//WHY I'M GETTING PROBLEM IN THIS LINE
    						//[Error] request for member 'left' in '* leaf', which is of non-class type 'node*' 
	Postorder(root->left,leaf);
    Postorder(root->right,leaf);
}

int main()
{
     struct node *root  = newNode(1);
     root->left         = newNode(2);
     root->right        = newNode(3);
   
     struct node* leaf=root;
     
     Postorder(root,&leaf);
   	 getchar();
     return 0;

}

Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements

public List<List<int>> ComputePowerSet(int[] nums)
        {
            List<List<int>> powerSet = new List<List<int>>();
            if (nums == null)
                return powerSet;
            bool[] bits = new bool[nums.Length];
            bool overFlowBit = false;
            while (!overFlowBit)
            {
                List<int> lst = new List<int>();
                for (int i = 0; i < nums.Length; i++)
                {
                    if (bits[i])
                        lst.Add(nums[i]);
                }
                //function PlusOne returns false if the end is reached i.e. 2^n 
                if (!PlusOne(bits))
                    overFlowBit = true;
                powerSet.Add(lst);
            }
            return powerSet;
        }

        public bool PlusOne(bool[] bits)
        {
            bool carry = true;
            //add i i.e. true to the bits
            int i = bits.Length-1;
            while (i >= 0 && carry)
            {
                bool b = bits[i];
                bits[i] = b ^ carry;
                carry = b & carry;
                i--;
            }
            //if carry is true implies reached the end i.e. 1111 + 1 = 0000, carry = 1
            return !carry;
        }

Programme 1

class A
{
    private:
    A()
   {

   }
};

int main()
{
   //Do not create an object of A 
}

Is there any error

Compile Time error Y/N
Run Time error Y/N

Programme 2

class A
{
   private:
   A()
   {  

   }
};

class B : public A
{

};

int main()
{
    //Do not create an object of A or B
}

Is there any error 
Compile time Y/N
Run Time Y/N

You have 5 data sources. There is a program which calls these data sources and returns a count value.

You need to speedup this program. How do you do that?
This is a sample code

int count = getCount(ds1);

if(count < 100 )
  count = count + getCount(ds2);
if(count < 100)
  count = count + getCount(ds3);
if(count < 100)
  count = count + getCount(ds4);
if(count < 100)
  count = count + getCount(ds5);

Make a function that shows the common elements in two arrays. Part 2: With duplicates (small explanation). Part3: without duplicates

Answer:

int[] intersect(int[] array1, int[] array2){
    if(array1.lentgh == 0 || array2.length == 0)
        return {};
    Set<Integer> set = new HashSet<Integer>();
    
    for(int i = 0; i < array1.length ; i++){
        set.put(array1[i]);
    }
    
    List<Integer> list = new ArrayList<Integer>();
    
    for(int i = 0;i < array2.length ; i++){
        if(set.contains(array2[i])){
            //map.put(map.get(array2[i])-1); //short explanation of how to do it with dupplicates
            set.remove(array2[i]);
            list.add(array2[i]);
        }
    }
    
    return list.toArray();
}

what will output of this

#include <iostream>
#include<algorithm>
using namespace std;

class Sum
{
  private:
          int s;
  public:
  Sum(int x):s(x)
  {
      
  }
  
  int getSum()
  {
      return s;
  }
  
  void operator()(int p)
  {
     s = s + p;   
  }

};

int main()
{
   cout << "Hello World" << endl; 
   
   int arr[] = {1,2,3,4,5,6,7,8};
   Sum obj = for_each(arr,arr+7,Sum(1000));
   cout<<obj.getSum()<<endl;
   
   return 0;
}

public class WithoutConditional {
	
	static void callme(String s) {
		System.out.println("string");
	}

	static void callme(Object s) {
		System.out.println("object");
	}

	public static void main(String[] args) {
		callme(null);
	}

}

The above code prints "string". Even if we change the order of the methods.
My question is why it doesn't print "object" as String is also instanceof Object. Passing null as argument shouldn't print "object" ???

Given a List of Students that are already sorted based on names, write a function to return list of students that is sorted based on grade (four possible grades are a,b,c and d). If two students has same grade, they should be sorted internally based on name.

I have written a code based on bucket sort. Something like this. Not sure whether this is optimal.

public List<Student> sortByGrade(List<Student> students)
{

	List<Student> aGradeStudents = new LinkedList<Student>();
	List<Student> bGradeStudents = new LinkedList<Student>();
	List<Student> cGradeStudents = new LinkedList<Student>();
	List<Student> dGradeStudents = new LinkedList<Student>();

	for(Student st : students)
	{

		switch(st.getGrade())
		{

			case 'a' :
			
				aGradeStudents.add(st);
				break;

			case 'b' :
			
				bGradeStudents.add(st);
				break;

			case 'c' :
			
				cGradeStudents.add(st);
				break;

			case 'd' :
			
				dGradeStudents.add(st);
				break;
		};

	}

	List<Student> sortedStudents = new LinkedList<Student>();

	sortedStudents.addAll(aGradeSudents);
	sortedStudents.addAll(bGradeSudents);
	sortedStudents.addAll(cGradeSudents);
	sortedStudents.addAll(dGradeSudents);
}

Given the following directory structure:

org

 | -- Robot.class

 | -- ex

      |-- Pet.class

     |

     |-- why

          |-- Dog.class

And the following source file:

class MyClass {

 Robot r;

 Pet p;

 Dog d;

Which statement(s) must be added for the source file to compile? (Choose all that apply.)

A. package org; 

B. import org.*; 

C. package org.*; 

D. package org.ex; 

E. import org.ex.*; 

F. package org.ex.why; 

G. package org.ex.why.Dog;

Given a binary search tree (BST) with each node having some value. You have to compute for each node the summation of all nodes whose value is greater than the current node.I have used the DFS kind of algorithm.

Dictionary<node,bool> visited = new Dictionary<node,bool>();
int Traverse(node n )
{
   if(node.Right == null)
       if(node.Left != null && !visited(node.Left))
          Traverse(node.Left);
           return node.value;
node.Summation = Traverse(node.Right);
if(node.Left != null && !visited(node.Left))
     Traverse(node.Left);
return node.Value + node.Summation;
}

i) Explain Polymorphism

ii) Output of the below code snippet :-

public class ParentTest {

	public int x = 0;

    public void print() {
        System.out.println("In Parent");
    }

}

public class ChildTest extends ParentTest {
	public int x = 1;

	public void print() {
        System.out.println("In Child");
    }
	
	public static void main( String args[] )
	{
		ParentTest s = new ChildTest();
		System.out.println(s.x);
		s.print();   
	}
}

public class Gen {

    public static void main(String[] args) {

        Integer i1 = new Integer(1);
        Integer i2 = new Integer(1);


        System.out.println(i1 != i2);
        System.out.println(i1 <= i2);
        System.out.println(i1 >= i2);


    }
}

WHY THE OUTPUT IS TRUE IN ALL CASES?

Given a mathematical expression, remove the redundant brackets from the expression.

e.g. input: (a + (b*c)) * (d * ( f * j) ) 
output should be: (a + b * c) *d * f * J

/* This class will be given a list of words (such as might be tokenized
 * from a paragraph of text), and will provide a method that takes two
 * words and returns the shortest distance (in words) between those two
 * words in the provided text. 
 * Example:
 *   WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
 *   assert(finder.distance("fox","the") == 3);
 *   assert(finder.distance("quick", "fox") == 1);
 * /

Given an array of non-repeating, non-sorted, positive and negative integers, find 4 numbers in that array which satisfy the following equation: A1 + A2 + A3 = A4

Complete the function to return the value A4. If no such numbers satisfy the given equation, return -1,

In case of multiple possibilities that satisfy the equation, return the largest such value of A4.

Sample Test Case:

Sample Input: {-6,2,4,8}

Sample Output: 4

Explanation: The value 4 can be achieved as follows: 8+2+(-6) = 4

IMPORTANT: You do not need to write full code. Just complete the given function.

/**This class find sequence of elements in an array which satifies a1+a2+a3=a4.
 * @author Kishor Kumar Padhan
 *
 */
public class EquationInArray {
	
	public static void main(String[] args) {
		
		int[] arr = new int[] {-6,2,4,8};
		int[][] arr1 = new int[arr.length*(arr.length-1)][2];
		int k=0;

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if(i!=j) {      
					arr1[k][0] = arr[i];
					arr1[k][1] = arr[j];
					k++;
				}
			}
		}

		int bigMatchedNumber=0;
		String bigMatchedEquation="";
		int m=0;
	
		while(m<arr1.length) {
			for(int n=0;n<arr.length;n++) {
				if(arr1[m][0]!=arr1[n][1] && arr1[m][1]!=arr1[n][1]) {	 
					int total = arr1[m][0]+arr1[m][1]+arr1[n][1];
					if(doesNumberExists(total,arr)) {
						if(total>bigMatchedNumber) {
							bigMatchedNumber=total;
							bigMatchedEquation = arr1[m][0]+"+"+arr1[m][1]+"+"+arr1[n][1]+"="+total;
						}
					}
				}
			}
			m++;
		}
		System.out.println("bigMatchedEquation : " + bigMatchedEquation);
	}

	private static boolean doesNumberExists(int total, int[] arr) {
		boolean matched = false;
		for (int i = 0; i < arr.length; i++) {
			if(total == arr[i]) {
				matched = true;
			}
		}
		return matched;
	}
}

/*
 * Returns true if the input string is a number and false otherwise
 */
 
public boolean isNumber(String toTest)
{
    // implementation here
}

/**
 * Implement a method which takes an integer array and returns an integer array (of equal size) in
 * which each element is the product of every number in the input array with the exception of the
 * number at that index.
 *
 * Example:
 *   [3, 1, 4, 2] => [8, 24, 6, 12]
 */
public int[] selfExcludingProduct(int[] input) {
    // implementation...
}

IF we remove next line character then program runs fine else it gives a seg fault

#include <stdio.h>

        void main()

        {

            char *a[10] = {"hi", "hello", "how"};

            int i = 0, j = 0;

            a[0] = "hey";

            for (i = 0;i < 10; i++)

            printf("%s\n", a[i]);

        }

In Amazon web site, the product items has to show with different attributes combination for clothers.

Example:
color - red blue green
size - XL X M S
pattern - checks lines

so output should be in below format in different combinations:

red - xL - checks
red - xL - lines
red - X - checks
red - x - lines
red - M - checks
:
:
green - S - checks
green - S - lines

Note:- In above example, no. of attributes is 3. but attributes can be N.

Below is the code, I have written. Hope it will be useful for anyone.

This is an non-recursive logic which will work for large value of N. time Complexity is O(n2).

-------------------------------------------------------------------------------------
package com.test;

import java.util.Scanner;
public class Solution 
{
	public static void main(String args[] ) throws Exception 
	{
		/* Enter your code here. Read input from STDIN. Print output to STDOUT */
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		in.nextLine(); //to read new line
		String[][] attributes = new String[n][];
		int i=0;
		while(i < n)
		{
			String temp = in.nextLine();
			String[] values = temp.split(" ");
			attributes[i] = values;
			i++;
		}
		printAttributesCombination(attributes);
	}

	static void printAttributesCombination(String[][] attributes)
	{
		int count[] = new int[attributes.length];
		int totalcount[] = new int[attributes.length];

		//initialize the totalcount and temp index count
		initialize(count, totalcount, attributes);

		while(isDone(count,totalcount))
		{
			printArray(attributes,count);
		}
	}

	static void initialize(int count[], int totalcount[], String[][] attributes)
	{
		for(int i = 0; i < count.length; i++)
		{
			count[i] = 0;
			totalcount[i] = attributes[i].length - 1;
		} 

		count[count.length-1] = -1;
	}

	static boolean isDone(int count[], int totalCount[])
	{
		boolean prevIndexSet = true;
		boolean canTerminateLoop = false;
		int i = 0;

		for(i = count.length - 1; i >= 0 ; i--)
		{
			if(count[i] == totalCount[i])
			{
				count[i] = 0;
				prevIndexSet = true;
				canTerminateLoop = true;
			}
			else
			{
				count[i] = count[i] + 1;
				prevIndexSet = false;
				canTerminateLoop = false;
			}
			if(!prevIndexSet)
				break;
		}

		if(canTerminateLoop  && i == -1 )
			return false;

		return true;
	}

	static void printArray(String[][] arr, int count[])
	{
		System.out.println();
		for(int i = 0; i < arr.length; i++)
		{
			System.out.print("  " + arr[i][count[i]]);
		}
	}
}
-------------------------------------------------------------------------------------

Output:
==============

Sample1:-
============
3
a b c
d e f
g h i

a d g
a d h
a d i
a e g
a e h
a e i
a f g
a f h
a f i
b d g
b d h
b d i
b e g
b e h
b e i
b f g
b f h
b f i
c d g
c d h
c d i
c e g
c e h
c e i
c f g
c f h
c f i

Sample2:-
============
4
a b
a b c
d e
f i

a a d f
a a d i
a a e f
a a e i
a b d f
a b d i
a b e f
a b e i
a c d f
a c d i
a c e f
a c e i
b a d f
b a d i
b a e f
b a e i
b b d f
b b d i
b b e f
b b e i
b c d f
b c d i
b c e f
b c e i

Write a recursive Method int shortestPath(int start, int end) in Java which returns the length of the shortest Path between start and end.

public class GraphMatrix {
	public GraphMatrix(int iNrOfNode){
		m_Matrix = new boolean[iNrOfNodes][iNrOfNodes];
	}
	private boolean[][] m_Matrix;
}

What would be the O/P and why?

#include<stdio.h>
#include<conio.h>

int main()
{
	

int k = -7; 
printf("%d", 0 < !k);

return 0;

}

Modify the following code to add a row number for each line is printed

public class Test {
	public static void main(String [] args){
		printParenthesis(3);
	}
	public static void printParenthesis(int n){
		char buffer[] = new char[n*2];
		printP(buffer,0,n,0,0);
	}
	public static void printP(char buffer[], int index, int n, int open, int close){
		if(close == n){
			System.out.println(new String(buffer));
		}else{
			if(open > close){
				buffer[index] = ']';
				printP(buffer, index+1, n, open, close+1);
			}
			if(open < n ){
				buffer[index] = '[';
				printP(buffer,index+1,n,open+1,close);
			}
		}
	}
}

Expected Output:

1.[][][]
2.[][[]]
3.[[]][]
4.[[][]]
5.[[[]]]

What changes needs to be done to accomplish the output expected?

Find a shortest path in a N*N matrix maze from (0,0) to (N,N), assume 1 is passable, 0 is not, 3 is destination, use memorization to cache the result. Here is my code. I am not sure if I am caching it right.

public static class MazeResult {
		public boolean solved;
		public List<String> res = new ArrayList<String>();
		public int steps = Integer.MAX_VALUE;
		public MazeResult(boolean isSolved) {
			solved = isSolved;
		}
	}

	static Map<String, MazeResult> cache = new HashMap<String, MazeResult>();
	static MazeResult solveMaze(int[][] m, int r, int c, List<String> path, HashSet<String> visited) {
		if (r < 0 || r >= m.length || c < 0 || c >= m[0].length)
			return new MazeResult(false);

		String cell = r + "" + c + "";
		if (m[r][c]==0 || visited.contains(cell))
			return new MazeResult(false);
		if (m[r][c] == 3) {
			MazeResult ret = new MazeResult(true);
			ret.res = new ArrayList<String>(path);
			ret.res.add(cell);
			ret.steps = path.size() + 1;
			return ret;
		}
		if (cache.containsKey(cell))
			return cache.get(cell);

		path.add(cell);
		visited.add(cell);
		MazeResult ret = new MazeResult(false), temp = new MazeResult(false);

		temp = solveMaze(m, r, c+1, path, visited);
		compareResult(temp, ret);

		temp = solveMaze(m, r, c-1, path, visited);
		compareResult(temp, ret);

		temp = solveMaze(m, r+1, c, path, visited);
		compareResult(temp, ret);

		temp = solveMaze(m, r-1, c, path, visited);
		compareResult(temp, ret);

		path.remove(path.size()-1);
		visited.remove(cell);
		
		cache.put(cell, ret);
		return ret;
	}

	private static void compareResult(MazeResult temp, MazeResult ret) {
		if (temp.solved) {
			if (temp.steps < ret.steps) {
				ret.res = temp.res;
				ret.steps = temp.steps;
			}
			ret.solved = true;
		}
	}

In Amazon's interview, Round 2 they asked question:

Write a program to print inorder traversal of two trees.

Both values must be printed alternatively.

e.g. if inorder traversal of tree 1 is 10, 15, 20 and tree 2 is 100, 150, 200 then it should print
10, 100, 15, 150, 20, 200.

I tried printing it recursively by calling 2 functions recursively (f1 calls f2, then f2 calls f1 and so on).

I don't know where my approach is going wrong? I know there are other ways to do it as well but in this approach what is the mistake?

public class HelloWorld{

 //this is the Node used in the tree
    static class Node{
        private int data;
        private Node left;
        private Node right;
        public Node(int data){
            this.data = data;
            left = null;
            right = null;
        }
        public void setLeft(Node left){
            this.left = left;
        }
        public void setRight(Node right){
            this.right = right;
        }
        public Node getLeft(){
            return this.left;
        }        
        public Node getRight(){
            return this.right;
        }
        public int getData(){
            return this.data;
        }
        public boolean equals(Node n){
            if(this.data ==(int) n.getData()) return true;
            else
                return false;
        }
    }

    public static void main(String[] args){
        HelloWorld bts = new HelloWorld();
        bts.run();
    }
    //execute the test case
    public void run(){
        Node root = new Node(10);
        insert(root,new Node(20));
        insert(root,new Node(50));
        insert(root,new Node(40));
        insert(root,new Node(15));
        
        
        Node node2 = new Node(100);
        insert(node2,new Node(200));
        insert(node2,new Node(500));
        insert(node2,new Node(400));
        insert(node2,new Node(150));
        
        
        //inOrderTraverse(node2);
        
        inOrderTraverse1(root, node2);
    }
     
    // insert a node to the binary search tree
    public void insert(Node root, Node n){
        if(root == null|| n == null) return;
         
        if(root.getData() > n.getData()){
            if(root.getLeft() == null){
                root.setLeft(n);
            }else{
                insert(root.getLeft(),n);
            }
 
        }else if(root.getData() < n.getData()){
            if(root.getRight() == null){
                root.setRight(n);
            }else{
                insert(root.getRight(),n);
            }             
        }
    }
    
    public void inOrderTraverse(Node node){
        if(node != null){
            if(node.getLeft() != null)
            inOrderTraverse(node.getLeft());
            System.out.print("  "+node.getData());
            if(node.getRight() != null)
            inOrderTraverse(node.getRight());
        }
         
    }
    
    //in-order Traversal
    public void inOrderTraverse1(Node node1, Node node2){
        if(node2 != null){
            inOrderTraverse2(node1, node2.getLeft());
            System.out.println("  "+node2.getData());
            inOrderTraverse2(node1, node2.getRight());
        }
    }
    
    public void inOrderTraverse2(Node node1, Node node2){
        if(node1 != null ){
            inOrderTraverse1(node1.getLeft(), node2);
            System.out.println("  "+node1.getData());
            inOrderTraverse1(node1.getRight(), node2);
        }
    }

Find the k-th Smallest Element in Two Sorted Arrays. I followed the algorithm from this post, http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
But it does not handle the case where there are duplicates? Does anyone know how to do that? Also, in Java, how should we reduce the size of the arrays? I used the code below, but did not work.

public static int kthSmallest2(int[] a, int[] b,  int k, int a_left, int a_right
			, int b_left, int b_right) {
		if (a_left==a_right)
			return b[k-1];
		else if (b_left==b_right)
			return a[k-1];
		
		int m = a_right-a_left, n=b_right-b_left;
		int i = (int)((double)m / (m+n) * (k-1));  // i can be any number
		
		// make sure i + j = k - 1
//		int i = (a_left+a_right)/2 + k/2;   // i can be any number
		int j = k - 1 - i;
		int bj_1 = 0, ai_1 = 0;

		if (i==0) {  ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound
		else {  ai_1 = a[i-1]; }
		if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound
		else {  bj_1 = b[j-1]; }

		if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j]
			return a[i];
		if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i]
			return b[j];

		if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must
			// reside before kth smallest, so also update k. 
			// also exclude b's upper bound, since they are all greater than kth element.
			return kthSmallest2(a, b, k, i+1, a.length-1, 0,j-1);
		else
			return kthSmallest2(a, b, k, 0, i-1, j+1, b.length-1);
	}

Explain the output of the following code:

int main( )
      {
	int x = 10, y = 20;/.
	x =!x;
	y =!x&&!y;
	printf(“x =%d y =%d”, x, y);
        return 0;
       }

why will the code show error when tried to compiled
below given is a C program snippet to get height of a binary tree.

int height (struct node * root)
{
	if(root=NULL)
	return 0;

	else
	{
		return max(height(root->left),	height(root->right))+1;
	}

}

int max(int a,int b)
{
	return ((a>b)?a:b);

}

Fill in the following methods:

public interface PointsOnAPlane {

    /**
     * Stores a given point in an internal data structure
     */
    void addPoint(Point point);

    /**
     * For given 'center' point returns a subset of 'm' stored points that are
     * closer to the center than others.
     *
     * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)
     *
     * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3)
     */
    Collection<Point> findNearest(Point center, int m);

}

public interface Intervals {
 
    /**
     * Adds an interval [from, to] into internal structure.
     */
    void addInterval(int from, int to);
 
 
    /**
     * Returns a total length covered by intervals.
     * If several intervals intersect, intersection should be counted only once.
     * Example:
     *
     * addInterval(3, 6)
     * addInterval(8, 9)
     * addInterval(1, 5)
     *
     * getTotalCoveredLength() -> 6
     * i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6]
     * [1,6] and [8,9] don't intersect so total covered length is a sum for both intervals, that is 6.
     *
     *                   _________
     *                                               ___
     *     ____________
     *
     * 0  1    2    3    4    5   6   7    8    9    10
     *
     */
    int getTotalCoveredLength();
}

if EVER + SINCE = DARWIN , then what is D+A+R+W+I+N?

Write a Program that takes an array of integers representing the heights of the trees in the row as input and prints the list of the visible trees.

Given a table of the form:
Product    Sold on
A           1/1/1980
B           1/1/1980
C           1/1/1980
A           1/1/1980
B           1/1/1980
C           2/1/1980
A           2/1/1980
There are 30 products and 10,000 records of such type. Also the month period during which sales happened is given to u.
Write the program to display the result as:
Product  Month     No. of copies
A           January       12
A           February     15
A           March         27
B           January        54
B           February     15
B           March         10
C           January        37

. We need to write the function to check the password entered is correct or not based on the following conditions..
a) It must have atleast one lower case character and one digit.
b)It must not have any Upper case characters and any special characters
c) length should be b/w 5-12.
d) It should not have any same immediate patterns like
abcanan1 : not acceptable coz of an an pattern
abc11se: not acceptable, coz of pattern 11
123sd123 : acceptable, as not immediate pattern
adfasdsdf : not acceptable, as no digits
Aasdfasd12: not acceptable, as have uppercase character

A chessboard was given to us. Where in there was a Knight and King was placed oncertain positions. Our aim is to reach the king from the knight in minimum no of counts.As we know, knight can either move 2 steps vertical/horizontal and 1 stephorizontal/vertical. same goes here as well. Proper image of the chess board was given inthe question paper, and all the positions(max 8) were given that knight can take in thefirst step. Sol : Most of us implemented using recursive func

Seat Reservation prog for the theatre. Write a function for seat allocation for the movietickets. Total no of seats available are 200. 20 in each row. Each row is referred by theCharacter, "A" for the first row and ,J, for the last. And each seat in a row is represented by the no. 1-20. So seat in diffrent rows would be represented asA1,A2....;B1,B2.....;........J1,J2... Each cell in the table represent either 0 or 1. 0 rep wouldseat is available , 1 would represent seat is reserved.Booking should start from the last row (J) to the first row(A). At the max 20 seats can be booked at a time. if seats are available, then print all the seat nos like "B2" i.e (2 row, 3col) otherwise Print "Seats are not available." and we must book consecutive seats only

suppose u r given a 4*3 rectangle like (take these values from user)Now u have to calculate the no. of squares in this rectangle like:No. of squares of dimension 1 is 12No. of squares of dimension 2 is 6No. of squares of dimension 3 is 2No. of squares of dimension 4 is 0Total no. of squares are 2

In given array find zero and replace the entire row and column with zeros 
    
    E.g Input:
    
    1   2   3   4
    5   6   7   8
    9   10  0   11
    12  13  14  15

    Output:
    
    1   2   0   4
    5   6   0   8
    0   0   0   0
    12  13  0   15

class NoName
 {
 children = new Hashtable()
 name = ""

 boolean hasChild(child: string)
 {
 return this.children.hasKey(child)
 }

 NoName addChild(child: string)
 {
 var childnode = new NoName()
 childnode.name = child
 this.children[child] = childnode
 return childnode
 }

 NoName getNode(child: string)
 {
 if this.hasChild(child)
 return this.children[child]
 else
 return this.addChild(child)
 }

 void addList(input: string)
{
 var currentNode = this.getNode(input[0])
 input = input.SubString(1, input.Length ? 1)
 if (input.Length < 1)
 currentNode.getNode("")
 else
 currentNode.addList(input)
 }

 string scan()
 {
 if (this.children.Values.Length == 0)
 return this.name
 if (this.children.Values.Length == 1)
 return this.name + this.children.Values[0].scan()

 var temp = new Array()
 foreach(child in this.children.Values)
 temp.Add(child.scan())

 return this.name + "{" + temp.Sorted().JoinArray(",") + "}"
 }
 }

 var x = new NoName()
 x.addList(’/home/user/foo’)
 x.addList(’/home/user/bar’)
 x.addList(’/home/user/baz/one’)
 x.addList(’/home/user/baz/two’)

 print x.scan()

Is there anyone can help me translate these code to java or tell me the result ,I will really appreciate it.Thanks

//Online Coding Assignment

As a member of the cab finder app team, you are tasked with implementing a CabFinder class that has the following minimal public interface:

class CabFinder implements CabStatusListener {
/**
* Initiates CabFinder. Called only once per app startup.
* @app An application object providing services implemented by
*      the rest of the application.
* @maxCabs Nearest number of cabs that can be returned to the user
*/
public void initialize(CabApp app, int maxCabs) {
  //Insert code here...
}

/**
* Gets nearest cabs within 1km of the current user’s location. 
* These must be the *nearest possible* @maxCabs in the 1km area.
* @return An unordered list of the nearest cabs.
*/
public Cab[] getNearestCabs() {
   //Insert code here...
}

/**
* Asynchronous Callback per CabStatusListener (see below). Called when the position of a cab has changed. 
*/
void onCabPositionChanged(Cab cab) {
   //Insert code here…
}

/**
* Asynchronous Callback per CabStatusListener (see below). Called when a cab’s availability changes.
* @cab The cab whose availability has changed
* @isAvailable true if the cab is now available, false otherwise
*/
void onCabAvailabilityChanged (Cab cab, boolean isAvailable) {
   //Insert code here…
}
}

Supporting Classes:
Here are the classes and utilities that are available for your use (you are not required to write any implementation for these classes)
/**
* Coordinates on a 2D map with a one meter granularity.
*/

class Position {
public int x;
public int y;
}

interface Cab {
	/**
      * Unique identifier of a cab.
      */
     int getID();
 
	/**
	* Gets the current position of the cab
	*/
  	Position getCabPosition();

	/**
	* Returns whether or not the cab is available
	*/
  	boolean isAvailable();
}

/**
* Provides services implemented by the rest of the Cab Application.
*/
interface CabApp {
/**
* Gets the current location of the user
*/
Position getUserPosition();

/**
* Returns an iterator that gives access to the list of all cabs in the city
*/
Iterator<Cab> getCabs();

/**
* Registers a CabStatusListener object for change notifications of cab object data.
*/
void register(CabStatusListener listener);
}

/**
* The CabStatusListener interface
*/
interface CabStatusListener {
/**
* Called when the position of a cab has changed.
* @cab The cab object
*/
void onCabPositionChanged(Cab cab);

/**
* Called when a cab’s availability changes.
* @cab The cab object
* @isAvailable true if the cab is available, false otherwise
*
*/
void onCabAvailabilityChanged (Cab cab, boolean isAvailable);
}

What is the output of following program:

1 #include <stdio.h>
  2
  3 int r = 1;
  4 int numbers[5] = {1, 2, 3, 1, 5 };
  5
  6 int main(int argc, char** argv)
  7 {
  8 #if !defined(_MSC_VER)
  9     asm("leal numbers, %esi");
 10     asm("movl $0, %ecx");
 11     asm("movl r, %eax");
 12     asm("label1:");
 13     asm("movl (%esi,%ecx,0x4), %ebx");
 14     asm("imul %ebx, %eax");
 15     asm("addl $1, %ecx");
 16     asm("cmpl $5, %ecx");
 17     asm("jl label1");
 18     asm("mov %eax, r");
 19 #else
 20     __asm
 21     {
 22         LEA ESI, numbers
 23         MOV ECX, 0
 24         MOV EAX, r
 25     label1:
 26         MOV EBX, [ESI + ECX * 4]
 27         IMUL EAX, EBX
 28         ADD ECX, 1
 29         CMP ECX, 5
 30         JL label1
 31         MOV r, EAX
 32     }
 33 #endif
 34     printf("Result= %d\n", r);
 35     return 0;
 36 }

Implement the function accumulate below in the language of your choice. The code is in PHP but the syntax of this question should translate into any language. You should have enough information from the comments to define this function correctly. You do not need to implement the function calc.
/**
* This interface should be implemented to represent doing a binary operation on two integers
*/

interface iBinaryOperator
{
/**
* This will take int $x and int $y and return an integer value or throw an exception
*
* @param int $x
* @param int $y
* @return int the value of the binary operation of $x and $y
* @throws MathException
*/
public function calc($x, $y);
}
/**
* This function should go through the array of operands and run calc on each operand IN ORDER, then
* return the accumulated value.
*
* For example the code below would echo the value 10:
*
* $op = new Addition(); //class Addition obviously implements iBinaryOperator
* $operands = array(5,2,3);
* echo accumulate($op, $operands);
*
* This function should work for ANY size array of operands, and ANY class that implements iBinaryOperator
*
* @param iBinaryOperator $op
* @param array $operands array of integers of size N, can be empty
* @return int|string returns an int on successful accumulation, or the string 'error' in error conditions
*/
function accumulate(iBinaryOperator $op, array $operands)
{//Add code here in the language of your choice

}

Given following definition, implement hashmap

Public class HashMap
{
	Public void put(object key, object value);
	Public void get(object value);

}

Reimplement this code so that its results will always be the same, but that it does not cause a stack overflow on large inputs. Your solution must still implement the Folder interface.

Coding
Your class must be named iteration.MyFolder

package iteration;

import java.util.Queue;

public class MyFolder<T, U> implements Folder<T, U>
{
    public U fold(U u, Queue<T> ts, Function2<T, U, U> function)
    {
        if(u == null || ts == null || function == null)
            throw new IllegalArgumentException();

        if (ts.isEmpty()) {
            return u;
        }

        // The recursive implementation will overflow the stack for
        // any data set of real size, your job is to implement a
        // non-recursive solution
        // return fold(function.apply(ts.poll(), u), ts, function);
        return null;
    }
}

package iteration;

import java.util.Queue;

public interface Folder<T, U>
{
    U fold(U u, Queue<T> list, Function2<T, U, U> function);
}


package iteration;

public interface Function2<T, U, R>
{
    R apply(T t, U u);
}

Print an n-ary tree with level. For e.g.

0                    foo
1          bar		baz
2 foobar		         	barfoo

Desired output:
Level 0: foo
Level 1: bar baz
Level 2: foobar barfoo

class TreeNode
{
	String name;
	List<TreeNode> getChildren();
}

void printLevels(TreeNode root)
{
	// -- CODE--
}

Find cousins of a given node in a Binary tree and BST.

My Approach:

Steps:(Using level order Traversal)
1. Create a queue  q and en-queue root element and take variable qSize and a flag=true
2. Start a loop and check queue is empty or not
    {
      if qSize==0 then qSize=q.size();
      if not flag then print the current queue (q)
      Start one more loop and check for qSize>0
      {      qSize--
             x=deque();
        if((x.left != null && x.left== key) || (x.right!= null && x.right== key))
       {
           flag=false
           continue
       }
       enqueue(x.left)
       enqueue(x.right)
      }
   }

How to find the number of static objects and dynamic objects created for a class?
Let say,

class MyClass
{
public:
};
int main()
{
MyClass cls;//Static Object
MyClass *obj = new MyClass();//Dynamic Object
...
...
//So on
}
void NewFun()
{
MyClass my;
MyClass *Obj1;
}

It should work for all the cases, like big or small projects

Given a binary tree, find out the maximum sum of value from root to each leaf.

find_Max(Node *root){
if (root==null)
return 0;
else
return max((find_Max(root->left), find_Max(root->right))+root->value;
}

determine the series of numbers entered (array a) from the encoded output of the program (array b).

For i from 0 to size - 1:
    For j from 0 to size - 1:
         b[(i+j)/32] ^= ((a[i/32] >> (i%32)) & (a[j/32 + size/32] >> (j%32)) & 1) << ((i+j)%32)

which are wrong statements in this code?

interface TestInterface{

void myMethod();

abstract void myMethod2();

private void myMethod3();

}

Can you predict the output of the following code?

for (int i = 0; i < 101; i++) {
			if (i % 2 == 0) {
				System.err.print(i);
			} else
				System.out.print(i);
		}

Given an integer N, print numbers from 1 to N in lexicographic order.

Details: To be implemented without using character conversion (or Strings).

Example:
N = 25

Print:
1
10
11
..
19
2
20
21
..
25
3
4
5
6
7
8
9

A simple solution using Strings (may not be acceptable):

System.out.print("\n\tLexicographic Order\n\nEnter an integer: ");
   Scanner input = new Scanner(System.in);
   Integer n = input.nextInt();
   List<String> list = new ArrayList<String>();
       
   for (int i = 1;i<n;i++){
     list.add(""+i);
   }
        
  Collections.sort(list);
        
  for (String j: list){
    System.out.println(j);
  }

explain if this method is thread safe?

public static  void myMethod(StringBuilder sb){
  // StringBuilder is not thread safe..
}

The question: given a binary tree, print all paths that sum to a certain value.

I've come up with the following approach (C++). This is different from other solutions I found on the web, that search the path list every time. I would appreciate your opinion regarding my attempt.

// Main function
void print_path_with_sum(Node* root, int expected_sum)
{
    if (!root) return;

    std::vector<Node*> path;
    search_to_bottom(root, path, 0, expected_sum);
    print_path_with_sum(root->left, expected_sum);
    print_path_with_sum(root->right, expected_sum);
}

// Helper function
void search_to_bottom(Node* node, std::vector<Node*>& path, int current, int expected_sum)
{
    if (!node) return;

    current += node->value;
    path.push_back(node);

    if (current == expected_sum) {
        print_path(path, 0, path.size());
    }

    search_to_bottom(node->left, path, current, expected_sum);
    search_to_bottom(node->right, path, current, expected_sum);
    path.pop_back();
}

Why are 2 boot loaders used in Android?
What is the use of each one and is it possible to remove any one of them and boot android?
Note: Two bootloaders are Xloader and Uboot.

#include<stdio.h>
  void main()
  {
          void *p;
          int x=10;
          float y=20.2;
          p=&x;
          printf("int %d\n",*p);
          *p=20;
          p=&y;
          printf("float %d\n",*p);
 }

What is the output?
If error, which error and correct the code.

How answer is coming as zero instead of garbage? Does compiler sets "0" to uninitialized variable?

#include<stdio.h>

void fun(void *p);
int i;

int main()
{
    void *vptr;
    vptr = &i;
    fun(vptr);
    return 0;
}
void fun(void *p)
{
    int **q;
    q = (int**)&p;
    printf("%d\n", **q);
}

its easy but still!!

find the largest subarray with equal number of 0's and 1's.
example 001010101
output:8

int  subarray(int arr[],int n)
{
int count=0;
for(int i=0;i<n;i++)
{
if(a[i]==0)
count++;
else
count--;
}
if(count==0)
return n;
else 
{
if(count>0)
return n-count;
else
return n+count;
}
}

Given a directed labelled graph in form of a knowledge base, and a query, write a parser which can return the edges and/or nodes requested in the query. (Knowledge base and queries are not case sensitive)
Knowledge base is given as input in a text file (input.txt).
For example a DAG can be represented as:

And the corresponding knowledge base for this DAG is :

(<Shelden>, <hasFriend>, <Raj>)
    (<Shelden>, <hasFriend>, <Leonard>)
    (<Shelden>, <worksAt>, <Caltech>)
    (<Leonard>, <worksAt>, <Caltech>)
    (<Raj>, <worksAt>, <Caltech>)
    (<Raj>, <age>,“30”)
     [Here 30 is a number and no edge can go out from this node while others like Nabraska, New_Delhi are entities, which can have further outgoing links.]
    (<Leonard>, <hasFriend>, <Penny>)
    (<Penny>, <bornIn>, <Nabraska>)
    (<Raj>, <bornIn>, <New_Delhi>)

A query can be written as :

Find persons who are friends?
Test case 1 : Select ?person1 ?person2 where { ?person1 <hasfriend> ?person2. }
The goal is to fill all the variable represented by ? with their values from knowledge base and return in csv format:
The result of this query is:
Person 1 Person 2
Shelden Raj
Shelden Leonard
Leonard Penny

The similar query can be extended to have joins also:

Find persons who are friends with Sheldon and the company/colleges to which his friends belong?
Test Case 2 : Select ?person ?university  where { <Sheldon> <hasFriend> ?person . ?person <worksAt> ?university. } 

Person  University
Leonard Caltech
Raj Caltech


Test Case 3 : Select ?person1 ?person2 where { ?person1 <worksAt> <Caltech> . ?person2 <bornIn < Nabraska> . ?person1 <hasFriend> ?person2 .}

Person 1    Person 2
Leonard          Penny


Test Case 5 : select * where {}
Output : Parse Error
How to approach this problem?

We have two strings: a normal alphanumeric string and a pattern string. the pattern string can be composed by alphanumeric chars plus the char "?" and "*"

We want to check if the first string match the pattern, where the ? means that every char (alphanumeric) is permitted in that position, while * allows to have a sequence of alphanumeric chars.

as test we want to check that the function returns true to the following calls.

isMatching("abab","abab")
isMatching("abab","a**b")
isMatching("ababab","ab*b")
isMatching("","*")
isMatching("aaaaaab","*?*b")

i found this question hard, since the language we want to parse is not L1 (there's an ambiguity in the parsing tree) it means that a backtrack modality must be implemented.

Took me a while to find a reasonable solution (that, to be honest i was not happy with)

function isLegal(string:String,pattern:String):Boolean{
	
	if(pattern.length == 0 && string.length == 0)
		return true;
	if(pattern.length == 0 && string.length > 0)
		return false;
	// NOT PROUD OF THE FOLLOWING CONDITION
	if(pattern.length == 1 && string.length == 0){
		if(pattern.charAt(0) == "*") return true;
	}

	if(isLetter(pattern.charAt(0))){
		if(string.charAt(0) == pattern.charAt(0)){
			// CHAR BY CHAR CONTROL
			return isLegal(string.substr(1),pattern.substr(1));
		}
		return false;
	} else if(pattern.charAt(0) == "?"){
		if(isLetter(string.charAt(0))){
		  	 // RECURSIVE CALL 
		  	 return isLegal(string.substr(1),pattern.substr(1));
		}
		return false;
	} else if(pattern.charAt(0) == "*"){
		var possibleSolution:Boolean = false;
		for(var i:int = 1; i< string.length && !possibleSolution;i++){
			possibleSolution = isLegal(string.substr(i),pattern.substr(1));
		}
		return possibleSolution;
	} else {
		// ILLEGAL PATTERN
		return false;
	}
}
function isLetter(s:String):Boolean{
	return s.charCodeAt(0) > 96 && s.charCodeAt(0)<122;
}

Search for an element in a matrix. Rows and columns of the matrix are sorted in ascending order. 


eg. matrix 
[1   14    25   35]
[2    16    28   38]
[5     20    28   40]
[16   22     38   41]   

search for 38. 

The interviewer was looking for a solution better than O(n+m). He didn't want a solution which starts searching from the left bottom and go to right or above according to the key value to search. That solution has O(n+m) worst complexity, where n is row count and m is column count.

Find the longest substring that is the same in reverse.

As an example, if the input was "I like racecars that go fast"
the answer would be "racecar".

Test your code in the following String:

"FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

class Test
{
    public void  m1(String arg1){
              arg1 = "Am I going to disappear?";
    }

public static void main (String[] args)
{
    Test test = new Test();
     String iAmOfAnArgumentativeNature = "I am born new";
            m1(iAmOfAnArgumentativeNature);
     System.out.print(iAmOfAnArgumentativeNature);
}
 }// end class

What is the output?

Write code to clone a graph recursively

struct Node
{
int data;
vector<struct Node*> neighbors;
}

Given an mxn matrix, design a function that will print out the contents of the matrix in spiral format.

Spiral format means for a 5x5 matrix given below:

[ 1 2 3 4 5 ]
[ 6 7 8 9 0 ]
[ 1 2 3 4 5 ]
[ 6 7 8 9 0 ]
[ 1 2 3 4 5 ]

path taken is:

[ > > > > > ]
[ > > > > v ]
[ ^ ^ > v v ]
[ ^ ^ < < v ]
[ < < < < < ]

where ">" is going right, "v" going down, "<" is going left, "^" is going up.

The output is:

1 2 3 4 5 0 5 0 5 4 3 2 1 6 1 6 7 8 9 4 9 8 7 2 3

This question was asked in todays interview's written test. According to me it should go into infinite waiting, but when I run this code on my computer, it safely ends up printing the value. I executed n number of times but still it finishes without without going into infinite waiting.

Can someone explain.

static class Job extends Thread {
        private int counter;

        @Override
        public void run() {
            synchronized(this) {
                for(int i = 0; i < 100000; i++)
                    counter++;
                
                this.notifyAll();
            }
        }
    }
    
    public static void main(String[] args) throws InterruptedException {
        Job job = new Job();
        job.start();
        synchronized(job) {
            job.wait();
        }
        
        System.out.println(job.counter);
    }

Given these 4 commands :

INCREMENT: 
    READ V
    WRITE V + 1

ZERO
    WRITE 0


ASSIGN : =

LOOP : FOR <integer> = <start> to <finish> do
	 	...
	     END FOR

Define these 4 functions: Decrement, Divide, test If equal (pseudo code).

You have an array of binary numbers as "00001101000001010100000..."... We need to find the First occurrence of 1 in this series.. using binary search.

we need to design an algorithm of complexity less than O(n).. and we need to use binary search strictly..

Using these 3 functions:

INCREMENT:
    READ N1
    WRITE N1 + 1

MINUS:
    READ N1, N2
    WRITE N1 - N2

MULTIPLY:
    READ N1,N2
    WRITE N1*N2

Define these four functions: Greater than, Equality, Nonequality, Divide.

given an array of charactes have to replace space with %20. where %20 is considered as 3 characters.write complete code to implement this.
ps: assume that array has enough space at the end that can fit one space character to 3 chacters(%20).

import java.io.*
char fn(char [] word)
{
    for(int i =1;i<=word.length();i++)
    {
        if(char[i]==" " && isArrayRightShiftable(word)){
            shiftArrayToRight(word,i);
            char[i]='%';
            char[i+1]='2';
            char[i+2]='0';
         }        
      }
    return word;

}
private boolean isArrayRightShiftable(char[] word)
{
    if(word.length()+2 < 50){
        return true;
        }
        return false;
}
private void shiftArrayToRight(char[] word, int i)
{
    for(int j = word.length();j>=i;j--)
    word[j+2]=word[j];
}

Find the maxProduct of three numbers from a given integer array.
1. Handle all the cases
2. Interviewer was looking for a complete code

public int maxPro()
{ // -5, -4, -3, -2 , 0
    Int array[] = new Int[]{4,5,6,0,-5,-7,-2,-10};
    Arrays.sort(array);
    // -10,-7,-5,-2,0,4,5,6
    int count =0;
    for(int i =0; i<array.length();i++){
        if(array[i]<0)
            count = count+1;
    }
    int maxProduct =1;
    if ( array.length()<3){
        return -1;
    }
    else if( array.length()>=3 ){
        int a=1; b=2;
              if(count>=2){
                  a = array[0]*array[1]*array[array.length-1];
                  b = array[array.length-1]*array[array.length-2]*array[array.length-3];
                  maxProduct = Math.max(a,b);
                  
              }
              else if (count == 0 || count == 1 || count == array.length()){
                  maxProduct = array[array.length-1]*array[array.length-2]*array[array.length-3];
              }
                      
    }        
    return maxProduct;
}

Suppose we want to convert one string S1 to another string S2 using only 3 types of operations:
-Insert(pos,char) (costs 8)
-Delete(pos) (costs 6)
-Replace(pos,char) (costs 8)
Find the sequence of steps to convert S1 to S2 such that the cost to convert S1 to S2 is minimum.
Eg. 'calculate' to 'late' - the possible operations are
Delete(0)
Delete(1)
Delete(2)
Delete(3)
Delete(4)
and the above sequence of operations costs 30.

I used the following code(using levenshtein algorithm) to solve this. But I am not getting correct answer.

tuples=[]
ops=[]
s1=''
s2=''
def levenshtein(a,b):
    global s1,s2
    n, m = len(a), len(b)
    if n > m:
        a,b = b,a
        n,m = m,n
    s1,s2=a,b
    current = range(n+1)
    for i in range(0,len(current)):
        current[i]=current[i]*8
    tuples.append(current)
    for i in range(1,m+1):
        previous, current = current, [i*8]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+6, current[j-1]+8
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change=change+8
            current[j] = min(add, delete, change)
        tuples.append(current)
    return current[n]

print levenshtein('calculate','late')
for i in range(len(tuples)):
    stri=''
    for j in range(len(tuples[0])):
        stri+=str(tuples[i][j])+' '
i=len(tuples)-1
j=len(tuples[0])-1
ops=[]
while i>0:
    while j>0:
        minimum=min([tuples[i-1][j],tuples[i][j-1],tuples[i-1][j-1]])
        if minimum==tuples[i-1][j]:
            i=i-1
            if not tuples[i][j]==tuples[i-1][j]:
                ops.append([1,i])
        elif minimum==tuples[i][j-1]:
            j=j-1
            if not tuples[i][j]==tuples[i][j-1]:
                ops.append([2,i-1,j])
        else:

            ops.append([3,i-1,s1[i-1]])
            i=i-1
            j=j-1

class a{
public:
	int a;
	virtual void sum() {
		printf("sum");
	}
};

class b : public a {
public:
	int b;
	virtual void sum() {
		printf("sum of class b");
	}
};

void main() {
	b aptr;
	a *bptr;
	bptr = &aptr;
	bptr->sum();
}

Output of the above program?

find a pattern in byte array and change that pattern in place (do not use temp array or variable)
for example, find pattern 0,0,3 in an byte array and replace it with 0,0
should be o(n)
my solutions :

Byte*remPattern003(byte arr[] , int &size) //size is input and output variable ///outputs size of  output array
{
	int k = 0;
	for(int i=0;i<size;)
	{
		if(arr[i] == 0 && arr[i+1] == 0 && arr[i+2] == 3)
		{
			arr[k++]=arr[i];
			arr[k++]=arr[i+1];
			arr[k]=arr[i+3];
			i+=3;

		}
		else
			arr[k++]=arr[i++];

	}
	size= k;
	return arr;
}

what will be the output of the following program and why...

#include<conio.h>
#include<stdio.h>

void main()
{
int a=10,b=20,diff;
diff=&a-&b;
printf("Difference=%d",diff);
float a1=10.0,b1=20.0;
diff=&a1-&b1;
printf("\nDifference=%d",diff);
char a2='a',b2='z';
diff=&a2-&b2;
printf("\nDifference=%d",diff);
double a3=10.0,b3=20.0;
diff=&a3-&b3;
printf("\nDifference=%d",diff);
getch();
}

XML Flat tree goes like this :

<?xml version="1.0" encoding="utf-8"?>
    <?xml-stylesheet type="text/xsl" href="Stack.xsl"?>
    <Items>
        <Item>
            <Id>1</Id>
            <ParentId>0</ParentId>
            <Name>1</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>2</Id>
            <ParentId>1</ParentId>
            <Name>1.1</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>3</Id>
            <ParentId>1</ParentId>
            <Name>1.2</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>4</Id>
            <ParentId>1</ParentId>
            <Name>1.3</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>5</Id>
            <ParentId>1</ParentId>
            <Name>1.4</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>6</Id>
            <ParentId>0</ParentId>
            <Name>2</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>7</Id>
            <ParentId>6</ParentId>
            <Name>2.1</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>8</Id>
            <ParentId>6</ParentId>
            <Name>2.2</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>10</Id>
            <ParentId>3</ParentId>
            <Name>1.2.1</Name>
            <SortOrder>0</SortOrder>
        </Item>
    </Items>
    </XML>

and to display the output like below

Assuming the XML parsing is done and now is in some data structure in memory
and write a C or C++ program to display the output as above...

I pressume that interview was expecting which data structure I may use to store
XML elements values and how do I retrieve the same.

I tried using Binary search tree however it needs to have max of 2 children
for each node. again thought of using array, which i thought is a bit
complicated compare to tree..

guess array would be one of the solutions like a[i][j][k]

for(i=0;i<m;i++
     {
      print (a[i] n );
      for (j=0;j<n;j++);
      print(a[i][j] n);
      for(k=0;k<p;k++)
      print(a[i][j][k] n);
     }

I feel tree would be more efficient way for programming this kind of
problems however I could find other than Binary search tree for programming
this again that is not a solution for this

I was asked to explain memento pattern.I explained with this example.

class Originator:ICloneable
    {
        public string a;
        public int b;
 
        public object Clone()
        {
            Originator o = new Originator();
            o.a = this.a;
            o.b = this.b;
            return o;
        }
    }
 
    class CareTaker
    {
        List<Originator> l = new List<Originator>();
 
        public void SaveMemento(Originator o)
        {
             l.Add((Originator)o.Clone());
        }
 
        public Originator RetrieveMemento(int i)
        {
            return l[i];
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            CareTaker c = new CareTaker();
            Originator o = new Originator();
            c.SaveMemento(o);
 
        }   
    }

The interviewer said this is is different from memto pattern ... can anyone explain where the difference is!!!

Print 'n' elements of fibonacci series.

public int fibonacci(int n) {
	if ((n == 1) || (n==2)) {
		System.out.print("\t" + 1);
		return 1;
	}
	int temp = fibonacci (n-1) + fibonacci (n-2);
	System.out.println("\t" + temp);
	return temp;

Find the k'th largest element in a binary search tree. Write code for

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

Node * kth_largest(Node *root, unsigned int k);

void populate(char **s);

int main() {
	char *s;
	populate(&s);
	printf("%s", s);	// should print "Prasad"
	free(s);
	return 0;
}

void populate(char **str) {
	// 1. The next two lines is one implementation
	*str = (char *)malloc(sizeof(char) * 7);
	strcpy(*str, "Prasad");

	// 2. This line seperately is another implementation
	*str = "Prasad";
}

What is wrong, if anything, with the two implementations of populate.

for this code:

class Interview {
        // input is max 3 chars
       public static int convertToString(int input) throws IllegalArgumentException;
}

write a method which checks whether the proper exception is being thrown.

write as many test cases for this : example : 123, 1, 2,... -123, 0,...

class Interview {
        // input is max 3 chars
       public static int convertToString(int input) throws IllegalArgumentException;
}

Given a binary tree return the level with maximum number of nodes

1
       / \
      2   3
      /\  /\
     4 5 6 7
    /       \
   8         9

Implement the Huffman compression algorithm as shown in the example below:

1) Given a string AAAAAABBCCDDEEFFFFF, group them according to the number of occurrences: A => 6, B => 2, C => 2, D => 2, E => 1, F => 5
2) Concatenate them according to their number of occurrences (adding the number of occurrences while doing it)
3) Put the concatenate strings in a tree-like structure:

ADEBCF(19)
                            / \
                           /   \
                          /     \
                         /       \
                        /         \
                       /           \
                      /             \
                    ADE(10)        BCF(9)
                    / \            / \
                   /   \          /   \
                  /     \        /     \
     A(6)   DE(4)   BC(4)   F(5)
                        / \            / \
                       /   \          /   \
                      /     \        /     \
                     D(2)   E(2)    B(2)   C(2)

What are the run time exceptions in java related to class and object creation??

class A{
...
dosomething();
..
}

class B extends A{
...
dosomething();
donothing();
...
}


class C expends A{

}
A a =new B();
a.donothing();   //which type of error
B b=new A();
A a1=new C();
B b=(b)a1;

Pls give input for anyother cases you may think better.

Program to calculate a pow n...

I gave a answer with O(logN)

public static long exp(int a , int n)
	{
		boolean is_N_Odd = false;
		if ( n % 2 > 0 )
		{
			n++;
			is_N_Odd =true;
		}

		if ( n == 2 )
			return a * a;
		else if (n == 1 )
			return a;
		else
		{
			long calc = exp (a , n/2) ;  
			if ( is_N_Odd )
				return calc * calc /a;
			else			
				return calc * calc ;
		}
	}

You are given two Strings lets say "S" which consist Upper Case albhabets and '?' character only and p. You are required to replace '?' with some alphabet so that resulting string have maximum number of "p" in it. You can replace '?' with any alphabet.
2. Replace '?' such that it should be lexicographically sorted.
Example
S="ABAAMA????MAZON????????"
p="AMAZON"
The final string S = "ABAAMAZONAMAZONAAAMAZON"

S="?????"
p="ABCD"
Final Result="AABCD"

Soln:- Proceed from the end of the String.

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int main()
{
    char S[]="ABAAMA????MAZON????????";
    char p[]="AMAZON";
     printf("%s  \n",S);
     int i,j,flag=0;
     i=i=strlen(S)-1;
     while(i>=0)
     {
    	int k=i;
    	for(j=strlen(p)-1;j>=0;j--)
    	{
    		if(S[k]==p[j] || S[k]=='?')
    		{
    		   k--;
                   flag=1;
                }
                else
                {
    		    flag=0;
	            break;
		 }		
    	}
        int m=i
        if(flag==1)
        {
        	for(j=strlen(p)-1;j>=0;j--)
        	{
                       if(S[m]=='?')
        		   S[m]=p[j];
                         m--;
        	}
        }
        else
        {
        	if(S[i]=='?')
        	   S[i]='A';
        }
        i--;
    }
    printf("%s",S);
}

What will be the minimum and maximum output of I

i=0;
threadA
{ i++;
i++;
i++;
}
threadB
{ i++;
i++;
i++;
i++;
i++;
}

public class Finder {
public static void main(String[] args){
System.out.println(X.Y.Z);
}}
class X{
static class Y{ static String Z ="Apple"; }
static W Y = new W();
}
class W{ String Z = "Orange";}

Please give the output with proper reason.

Write a function to check whether the two strings are rotation of each other or not.
Example: str1="Password" str2="ordPassw"
My Solution was.........

#include<stdio.h>
void fn(char * str1, char * str2)
{
    int i=0, j=0,flag=0;
    while(str2[i])
    {
        if(str2[i]== *str1)
        {
            flag=1;
            break;
        }
        i++;
    }
    if(!flag)
    {
        printf("2nd String is not a rotation of other\n");
        return;
    }
    j=i;
    while(str2[i])
    {
        if( !(str2[i]==*str1))
        {
            printf("2nd String is not a rotation of other\n");
            return;
        }
        i++;
        str1++;
    }
    i=0;
    while(i<j)
    {
        if( !(str2[i]==*str1))
        {
            printf("2nd String is not a rotation of other\n");
            return;
        }
        i++;
        str1++;
    }
    if(*str1=='\0')
        printf("String are rotation of each other\n");
    else
        printf("2nd String is not a rotation of other\n");
}


int main()
{
    char * str1="Password";
    char * str2="ordPassw";
    fn(str2, str1);
    return 0;
}

This was at a recent written test...
There is a toycar placed on a 5 by 5 board.We can give 5 commands to it ,
PLACE(X,Y,F) where x denotes X Axis,y denotes Y Axis and F denotes the direction to which its facing.
MOVE->Move will move the toycar one step in the direction where its facing
LEFT->Left will turn the toycar by 90 degrees to its left and face it to the new direction .Note:Left will not move the toycar, it will just change the direction
RIGHT->Right will turn the toycar by 90 degrees to its right and face it to the new direction .Note:Right will not move the toycar, it will just change the direction
REPORT->Report shall tell me the X Axis,YAxis and Direction of the toycar. like 0,0,NORTH

Note:You cannot move,left,right,report the toycar unless you place it.

Assume its a Prod level code, Solve it in Java only.
Below is my code and I haven't been selected, please tell me if there is better way to do it because my solution is correct but probably very basic.Thanks.

package com.ds;

public class ToyCar {
	
	private ToyCar toycar;
	private boolean isToyPlaced;
	private int xAxis,yAxis;
	private enum Direction {EAST,WEST,NORTH,SOUTH};
	private Direction direction;
	public int getxAxis() {
		return xAxis;
	}
	public void setxAxis(int xAxis) {
		this.xAxis = xAxis;
	}
	public int getyAxis() {
		return yAxis;
	}
	public void setyAxis(int yAxis) {
		this.yAxis = yAxis;
	}
	public Direction getDirection() {
		return direction;
	}
	public void setDirection(Direction direction) {
		this.direction = direction;
	}
	
	ToyCar(){
		
	}
	
	public ToyCar(int xAxis,int yAxis,Direction direction) {
		
		this.xAxis=xAxis;
		this.yAxis=yAxis;
		this.direction=direction;
	}
	
	public void place(int x,int y, Direction d){
		
		if(x<0||x>5||y<0||y>5 || d==null){
			System.out.println("Place Error:Attempt to place toy outside the box");
			return;
		}
		toycar = new ToyCar(x, y, d);
		isToyPlaced=true;
	}
	
	public void move(){
		if(!isToyPlaced){
			System.out.println("Move Error:Attempt to Move Toy without placing in board");
			return;
		}
		if(toycar.getDirection().equals(Direction.EAST)){
			int newPosition=toycar.getxAxis()+1;
			if(newPosition<0||newPosition>5){
				System.out.println("Move Error:Attempt to place toy outside the box");
				return;
			}
			toycar.setxAxis(newPosition);
		}else if(toycar.getDirection().equals(Direction.WEST)){
			int newPosition=toycar.getxAxis()-1;
			if(newPosition<0||newPosition>5){
				System.out.println("Move Error:Attempt to place toy outside the box");
				return;
			}
			toycar.setxAxis(newPosition);
		}else if(toycar.getDirection().equals(Direction.NORTH)){
			int newPosition=toycar.getyAxis()+1;
			if(newPosition<0||newPosition>5){
				System.out.println("Move Error:Attempt to place toy outside the box");
				return;
			}
			toycar.setyAxis(newPosition);
		}else if(toycar.getDirection().equals(Direction.SOUTH)){
			int newPosition=toycar.getyAxis()-1;
			if(newPosition<0||newPosition>5){
				System.out.println("Move Error:Attempt to place toy outside the box");
				return;
			}
			toycar.setyAxis(newPosition);
		}
	}
	
	public void left(){
		
		if(!isToyPlaced){
			System.out.println("Left Error:Attempt to Move Toy without placing in board");
		}
		if(toycar.getDirection().equals(Direction.EAST)){
			toycar.setDirection(Direction.NORTH);
		}
		else if(toycar.getDirection().equals(Direction.WEST)){
			toycar.setDirection(Direction.SOUTH);
		}
		else if(toycar.getDirection().equals(Direction.NORTH)){
			toycar.setDirection(Direction.WEST);
		}
		else if(toycar.getDirection().equals(Direction.SOUTH)){
			toycar.setDirection(Direction.EAST);
		}
		
	}

	public void right(){
		
		if(!isToyPlaced){
			System.out.println("Right Error:Attempt to Move Toy without placing in board");
		}
		if(toycar.getDirection().equals(Direction.EAST)){
			toycar.setDirection(Direction.SOUTH);
		}
		else if(toycar.getDirection().equals(Direction.WEST)){
			toycar.setDirection(Direction.NORTH);
		}
		else if(toycar.getDirection().equals(Direction.NORTH)){
			toycar.setDirection(Direction.EAST);
		}
		else if(toycar.getDirection().equals(Direction.SOUTH)){
			toycar.setDirection(Direction.WEST);
		}
		
	}
	
	public void report(){
		
		if(!isToyPlaced){
			System.out.println("Report Error:How can i report when I am not on board");
			return ;
		}
		System.out.println(toycar.getxAxis()+" , "+toycar.getyAxis()+" , "+toycar.getDirection());
		
	}
	
	public static void main(String[] args){
		
		ToyCar to = new ToyCar();
		to.place(0, 0, Direction.WEST);
		to.left();
		to.move();
		to.report();
	}

}

needed to turn a sequential Actions into parallel implementation

static string FlNm = Environment.CurrentDirectory, URL = "", TmpHtm = "";

            enum Act
            {
                dolar, ValidateTimeOut
            }

            void Execute(Act Exc)
            {


                switch (Exc)
                {
                    case Act.dolar:
                        URL = "http://www.boi.org.il/he/Markets/ForeignCurrencyMarket/Pages/Default.aspx";
                        FlNm += "\\TempHtm.htm";
                        TmpHtm = AgilityPacDocExtraction(URL).GetElementbyId("Dv_Main").InnerHtml;
                        File.WriteAllText(FlNm, TmpHtm);
                        break;
                    case Act.ValidateTimeOut:
                        URL = "http://hm.hental.co.il/timeclock/tcreportall/WorkDaysPerMonth.aspx?Cstate=Link";
                        FlNm += "\\TempHtm.htm";
                        TmpHtm = AgilityPacDocExtraction(URL).GetElementbyId("anyId").InnerHtml;
                        File.WriteAllText(FlNm, TmpHtm);
                        break;

                }

            }







            public HtmlAgilityPack.HtmlDocument AgilityPacDocExtraction(string URL)
            {


                using (WC = new WebClient())
                {
                    WC.Proxy = null;
                    WC.Encoding = Encoding.GetEncoding("UTF-8");
                    tmpExtractedPageValue = WC.DownloadString(URL);
                    retAglPacHtmDoc.LoadHtml(tmpExtractedPageValue);
                    return retAglPacHtmDoc;
                }

}

Write a recursive procedure, called laceStringsRecur(s1, s2), which also laces together two strings. Your procedure should not use any explicit loop mechanism, such as a for or while loop. We have provided a template of the code; your job is to insert a single line of code in each of the indicated places.

def laceStringsRecur(s1, s2):
    """
    s1 and s2 are strings.

    Returns a new str with elements of s1 and s2 interlaced,
    beginning with s1. If strings are not of same length, 
    then the extra elements should appear at the end.
    """
    def helpLaceStrings(s1, s2, out):
        if s1 == '':
            #PLACE A LINE OF CODE HERE
        if s2 == '':
            #PLACE A LINE OF CODE HERE
        else:
            #PLACE A LINE OF CODE HERE
    return helpLaceStrings(s1, s2, '')

Find the subsequences whose elements should not be adjacent and their sum should be maximum from the given array (contains only positive integers).
Eg: int[] A = {10, 1, 3, 25}
Sol: Sum: {10, 3} = 13
{1,25} = 26
{10,25} = 35
Here the Maximum subsequence is {10, 25}.

#include<stdio.h> #include<stdlib.h> 
int main(){
    union A {  
         long int y[5];  
              union B{  
                    double g; 
                    union C{  
                           int k;
                           union D{ 
                                 char ch;
                                 int x[5]; 
                           } s; 
                     }a;  
                }b; 
          }*p;
          p=(union A * ) malloc ( sizeof (union A));  
          p->b.a.k=15;
          printf("%d %d \n",p->b.a.s.x[0],p->y[0]);  
}

output : 15 15
plz explain with working

//what will be the output of the program if characters 'hello world' and enter are supplied to the program ?

#include<stdio.h>
int main()
{
    void fun();
    fun();
    printf("\n");
    return 0;
   
}

void fun()
{
     char c;
     if((c=getchar())!= '\n')
                        fun();
                        printf("%c ", c);
                        
                        }

output : d l r o w o l l e h
(plz Explain...)

I/P:1234abcd  in array
O/P:1a2b3c4d
constraint:In-place.........with out using any extra buffers....though it's rational to use temporary variables. time comolexity o(n)

output and why ?

#include<iostream>
class con
{
      struct node
      {
             int data;
                int rest;

      };
    public:
           con()
           {}
           };

     int main()
     { con c;
        std::cout<<"size of con class ="<<sizeof(c);
return 0;
}

: Design a data structure for the following operations:

I. Enqueue

II. Dequeue

III. Delete a given number(if it is present in the queue, else do nothing)

IV. isNumberPresent

All these operations should take O(1) time

what will be output ?

class z
{
};

class x
{
int a;
};

int main()
{
std::cout << sizeof(X) << '\n';
std::cout << sizeof(z) << '\n';
}

The shortest code by character count that takes a single input integer N (N >= 3) and returns an array of indices that when iterated would traverse an NxN matrix according to the JPEG "zigzag" scan pattern.

For Ex

1 2 3
(Input) 3  -->  4 5 6  --> 
                       7 8 9

Output--> 1 2 4 7 5 3 6 8 9 


                           1  2   3   4
(Input) 4  -->  5  6   7   8  
                      9 10 11 12
                     13 14 15 16
                     

output  1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16

how many times the base class are called in the following code.

class Base
{
}
class D1:public Base
{
}
class D2:virtual public Base
{
}
class DD: public D1, public D2
{
}
int main()
{
DD cObj;
}

Give the output of the following code:

#include<iostream>
using namespace std;

int main()
{
int a=10,b=2;
b=a+++a;
cout<<b<<" "<<a"\n";
return 0;
}

#include <iostream>
using namespace std;

class base{
public:
virtual void func(int i,int j=10)
{
cout<<"base func"<<endl;
}
};


class der:public base
{
public:
void func(int i,int j)
{
cout<<"der "<<j<<" func"<<endl;
}
};


int main()
{
der dd;
base *bb = new der();
bb->func(10);
dd.func(10,1);
}

What is the output of this.

Why ans is 2 for both
--

int main() {
int x = 1;
x=x++/++x;
printf("%d\n",x);
return 0;
}

======and======

int main() {
int x = 1;
x=++x/x++;
printf("%d\n",x);
return 0;

}

1.Design a vending machine in java.takes coins of 2,3,7,JAVA
2.Design one/two player tic-tac-toe,Java.
3.sort array {0,1,1,0,1,0,1,0,0,1,1,1,0} of binary numbers in O(n) time complexity using property of binary numbers.(no counting here)
4.Design/implement a Hashset class of your own.
5.Memory dumps in java


....................................................................................

int[] array = {3,-1,-2,2,2,3,2,-6,2,3,-8,0,2};
out put needed :
{3,2,2,3,2,2,3,0,2,-1,-2,-6,-8}
order is maintained and -ve numbers are sent to rightmost in order.

Design a code with single iteration to do it.

What is wrong with the below code?

#include <iostream>
#include <string.h>
using namespace std;
 
 
class A
{
        char *p;
        public:
        A(const char* str)
        {
                p=new char[strlen(str)+1];
                strcpy(p,str);
        }
 
        ~A()
        {
                delete p;
        }
};
 
int main()
{
        A s("Object s");
        A t=s;
        s.~A();
        A u("Object u");
        u=s;
        return 0;
}

#include<stdio.h>
void main(){

int x,y,z;
x=y=z=1;
z=++x||++y&&++z;
printf("%d %d %d \n",x,y,z);
getch();
}

what is the output n explain the output!!!!

what will be the o/p of the following program:

main()
{
  int ret;
  ret=fork();
  ret=fork();
  ret=fork();
  ret=fork();

  if(!ret)
    printf("one");
  else
    printf("two");
}

void freeList( struct node *n )
{
	while( n )
	{????}
}

Which one of the following can replace the ???? for the function above torelease the memory allocated to a linked list?
Choice 1 	n = n->next;
		free( n );

Choice 2 	struct node m = n;
		n = n->next;
		free( m );

Choice 3 	struct node m = n;
		free( n );
		n = m->next;

Choice 4 	free( n );
		n = n->next;

Choice 5 	struct node m = n;
		free( m );
		n = n->next;

void *ptr;
myStruct myArray[10];
ptr = myArray;
Which of the following is the correct way to increment the variable "ptr"?
Choice 1 ptr = ptr + sizeof(myStruct);
Choice 2 ++(int*)ptr;
Choice 3 ptr = ptr + sizeof(myArray);
Choice 4 increment(ptr);
Choice 5 ptr = ptr + sizeof(ptr);

I have given a Long Sentence and some words(to be searched in the sentence), i have to find the smallest part of the sentence which contains all the words to be Searched in that Sentence and print that part.

I have tried it, 1. First get all locations(indexes) of all words from the given sentence. 2. then try to find smallest part from these indexes of words.

But i am having problem implementing 2nd part . So i want some advice for it or if you suggest any other algorithm which can make it fast.
Example: If i have a String > "Hello, my name is undefined. but your name is not undefined." and i have to search word [is, undefined] then the answer should be printed is: is undefined //which is taken from the sentence 1st and we can not print from second sentence as it is " is not undefined" because it is not shortest.

import java.util.*;
import java.io.*;
public class ShotestSubSegment2 
{
static SearchStr[] search;
static String copystr;
public static void main(String s[])
{
try
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        copystr = str.substring(0).toLowerCase();
        int k = Integer.parseInt(in.readLine());
        search = new SearchStr[k];
        for(int i=0;i<k;i++)
        {
            search[i] = new SearchStr(in.readLine().toLowerCase());
            getIndicesOf(search[i]);
            if(search[i].noOfElements()==0)
            {
                System.out.println("No Segments Found");
                return;
            }
        }
        searchSmallestPart();//Dont getting Idea Of this

    }
    catch(Exception x){}
}

public static void getIndicesOf(SearchStr searchS) 
{
    String searchStr = searchS.getName();
    int startIndex = 0, searchStrLen=0;
    int index;
    searchStr = searchStr.toLowerCase();
    searchStrLen = searchStr.length();
    while ((index = copystr.indexOf(searchStr, startIndex)) > -1) 
    {
        searchS.add(index);
        startIndex = index + searchStrLen;
    }
}

}

A very interesting question. Still awaiting answer so posting again.

What does this method do?

Stuff is a object in java with two members someStuff and anotherStuff


public static Stuff doSomeStuff (Stuff s0, Stuff s1) {
        Stuff someStuff = s1.getSomeStuff();
        if(someStuff != null){
            s1.setSomeStuff(doSomeStuff(null, someStuff));
        }



if(s1.getAnotherStuff()==null){
s1.setAnotherStuff(s0);
return s1;
} else {
Stuff myStuff = doSomeStuff(s1,s1.getAnotherStuff());
s1.setAnotherStuff(s0);
return myStuff;
}
}

Does it have any bugs or edge cases where it will not execute?
Describe the time complexity of the function and comment on its effectiveness.

Without using extra space place all zeroes to left and 1's to right from an array of Zero's and 1's as below
011001 ans. 000111

public class Zeros_ones_New {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arrZerosOnes = { 0,1,0,1,0,1,1 };
		int len = arrZerosOnes.length;
		int firstOne = -1;
		int lastZero = len;
		for (int i = 0; i < len; i++) {
			if (arrZerosOnes[i] == 1) {
				firstOne = i;
				break;
			}
		}

		for (int u = len - 1; u > -1; u--) {
			if (arrZerosOnes[u] == 0) {
				lastZero = u;
				break;
			}
		}

				
		if (firstOne > -1 && lastZero<len) {
			while (firstOne<lastZero) {

				for (int j = firstOne; j < lastZero; j++) {
					if (((j + 1) <= lastZero) && (j == firstOne)
							&& (arrZerosOnes[j + 1] == 0)) {
						arrZerosOnes[j] = 0;
						arrZerosOnes[j + 1] = 1;
						firstOne++;
						/*if ((j + 1) == lastZero) {
							break;
						}*/
					} else if (((j + 1) <= lastZero) && (arrZerosOnes[j] == 1)
							&& (arrZerosOnes[j + 1] == 0)) {
						arrZerosOnes[j] = 0;
						arrZerosOnes[j + 1] = 1;
						if ((j + 1) == lastZero) {
							lastZero--;
						}
					}
				}
			}
		}

		for (int t = 0; t < len; t++) {
			System.out.print(arrZerosOnes[t]);
		}
	}

}

How to check a whether a very big number n^n = k

How to most efficiently find duplicates/commons in two sorted arrays of integers. No extra space should be used. My answer as below

public class Duplicate {

	//private HashSet<Integer> duplicates = new HashSet<Integer>();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int a[] = {0,2,2,4,6,8,8,9,9,10};
		int b[] = {0,3,3,4,8,8,10,12};
		
		new Duplicate().mergeAndCheck(a, b);

	}
	
	private void mergeAndCheck(int[] arr1, int[] arr2){
		int len1 = arr1.length;
		int len2 = arr2.length;
		
		int pointArr1 = 0;
		int pointArr2 = 0;
		while((pointArr1<len1)&&(pointArr2<len2)){
			if(arr1[pointArr1]<=arr2[pointArr2]){
				if((arr1[pointArr1]==arr2[pointArr2])){
					
					if(pointArr1==0){
						System.out.print(" "+arr1[pointArr1]);
					}else if(arr1[pointArr1]!=arr1[pointArr1-1]){
						System.out.print(" "+arr1[pointArr1]);
					}
					//duplicates.add(arr1[pointArr1]);
					
				}
				pointArr1++;
				
			}else{
								
				pointArr2++;
							
			}
		}
		
		/*for(Integer iNT:duplicates){
			//System.out.print("  "+iNT);
		}*/
		
	}

}

what is the o/p of following along with justifying logic ?

#include<stdio.h>
       main()
{    
  int i=0;
  prrintf("%%%%");
}

What does this method do?

Stuff is a object in java with two members someStuff and anotherStuff

public static Stuff doSomeStuff (Stuff s0, Stuff s1) {
        Stuff someStuff = s1.getSomeStuff();
        if(someStuff != null){
            s1.setSomeStuff(doSomeStuff(null, someStuff));
        }

        if(s1.getAnotherStuff()==null){
                s1.setAnotherStuff(s0);
                return s1;
        } else {
                Stuff myStuff = doSomeStuff(s1,s1.getAnotherStuff());
                s1.setAnotherStuff(s0);
                return myStuff;
        }
}

What does this method do? Does it have any bugs or edge cases where it will not execute?
Describe the time complexity of the function and comment on its effectiveness.

I was given a very interesting question.
You are given two very large files each containing integers in each line followed by a line break.

Produce a file with integers that are common in both files.

Estimate the time complexity of your code block?

Any edge cases and Bottlenecks?

Assumptions?
How would you solve this.

I did a little research on this and saw that some people suggested using Radix Sort for this and trying to split on large file into subsets and then using radix sort.

Here is the link

http://stackoverflow.com/questions/6520954/produce-a-file-that-has-integers-common-to-two-large-files-containing-integers

Can someone help me write this function. I read a lot of theories a lot of places but I am really looking for a code, preferably java for this.

This is a simple implementation of the same. I got a clarification that numbers are integers but the files are large but on one disk only.

I am using an approach as In case the file is too big to fit into memory on one go, break it into parts or read n integers at a time.and then use hashmaps to look for integers.

Cpmplexity: If the partition size is p and the file size is m then and no of rows per partition in n then ----- O(m/p * n) or O(N).

import java.io.*;
import java.util.*;
import java.io.FileWriter;

public class FileRead{

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
   
    File file1 = new File("C:\\Documents and Settings\\chaos\\Desktop\\input1.txt");   
    File file2 = new File("C:\\Documents and Settings\\chaos\\Desktop\\input2.txt");
    try{
       
    Map mymap = new HashMap();
    Scanner scan1 = new Scanner(file1);
    Scanner scan2 = new Scanner(file2);
    
    
    
    while(scan1.hasNextLine(    ))
    {
        int line = scan1.nextInt();
        mymap.put(line,1);
    }
   
    while(scan2.hasNextLine())
    {
        int line = scan2.nextInt();
        try{
        int val = (Integer) mymap.get(line);
             if(val==1)
            
             try{
                    FileWriter f1 = new FileWriter("C:\\Documents and Settings\\chaos\\Desktop\\output.txt");
                    BufferedWriter out = new BufferedWriter(f1);
                    out.write(line);
                    System.out.println(line);
                    }catch (IOException e){}
             
        }catch(NullPointerException e2){}
    
    }
    } catch(FileNotFoundException e){e.printStackTrace();}
    
    }

}

Reverse K elements of a linked list.
Solved on 31st May.
It still has one bug, if the number of elements in a linked list are not a multiple of K, then it truncates the linked list at a multiple of K.
1->2->3->4->5->6 becomes
3->2->1->6->5->4 for K=3

Eg. if K=5 and number of elements is 12, it will reverse till 10 th element and then truncate it. so when the reversed list is printed, only 10 elemtns with every 5 revesed is shown, need to fix this.

package ThreadPkg;

import java.util.*;

class link
{
    int data;
    public link nextlink;
    link(int d1)
    {
        data = d1;
    }}

class List{
    
    link head;
    static int rev;
    link revhead;
    List(){
    head = null;
    Scanner scan1 = new Scanner(System.in);
    rev = scan1.nextInt();
   }

    
    boolean isEmpty(link head)
    {
        return head==null;
    }
    
    void insert(int d1)
    {
        link templink = new link(d1);
        templink.nextlink = head;
        head = templink;
    }
    
    void printlist(){
        link head1 = head;
        while(!isEmpty(head1))
            {
            System.out.print(head1.data + " ");
            head1 = head1.nextlink;
            }
        System.out.println();
            }

    void reverse()
    {
        boolean flag=true;
        revhead = head;
        link previous=revhead,temp=null,temp2=null;int i=1;
        while(true)
    {
     i++;
        
    for(int j=0;j<(2*rev-1);j++)
    {
        if(isEmpty(previous))
        {
     // 	previous=temp2;
        	break;
        }
        temp2=previous;
        previous=previous.nextlink;
        
    }
        
            for(int k=0;k<rev;k++)
            {
       if(isEmpty(revhead))
        {
            return;
        }
             
        		temp = revhead.nextlink;
                revhead.nextlink = previous;
                previous = revhead;
                revhead = temp;
            }
            
        if(flag){
            head=previous;
        flag=false;
        }
         previous=temp;
        }
       
    }
    }

class RevKLinkedList {

    public static void main(String[] args) {
        
        
    	List list1 = new List();
        
        list1.insert(10);
        list1.insert(20);
        list1.insert(30);
        list1.insert(40);
        list1.insert(50);
        list1.insert(60);
        list1.insert(70);
        list1.insert(80);
        list1.insert(90);
        list1.insert(100);
        list1.insert(110);
        list1.insert(120);
        list1.printlist();
        list1.reverse();
        list1.printlist();
        }
}

The second round interview: Implement a binary tree with the given interface, then discuss the implementation via remote desktop and phone.

/*
 * An interface for an sorted binary tree.
 * 
 * The interface provides methods for inserting values, checking if certain values are contained and iterating over the elements.
 * Note: Implementing classes should provide an iterator that traverse the inserted object in the sorted order.
 */
public interface IBinTree<V extends Comparable<V>> extends Iterable<V> {
	/*
	 * Insert an object into the binary tree. Note: The tree should be sorted, inserting the same object twice is allowed but the insert is expected to be stable.
	 */
	void insert(V obj);
	/*
	 * Batch-insert multiple elements.
	 */
	void insert(Vector<V> vec);
	/*
	 * Check if the object is already in the tree. Return true if it is, false otherwise. 
	 */
	boolean contains(V obj);
}

Reverse K elements of a linked list.
Solved on 31st May.
It still has one bug, if the number of elements in a linked list are not a multiple of K, then it truncates the linked list at a multiple of K.
Eg. if K=5 and number of elements is 12, it will reverse till 10 th element and then truncate it. so when the reversed list is printed, only 10 elemtns with ever 5 revesed is shown, need to fix this.

import java.util.*;

class link
{
    int data;
    public link nextlink;
    link(int d1)
    {
        data = d1;
    }}

class List{
    
    link head;
    static int rev;
    link revhead;
    List(){
    head = null;
    Scanner scan1 = new Scanner(System.in);
    rev = scan1.nextInt();
   }

    
    boolean isEmpty(link head)
    {
        return head==null;
    }
    
    void insert(int d1)
    {
        link templink = new link(d1);
        templink.nextlink = head;
        head = templink;
    }
    
    void printlist(){
        link head1 = head;
        while(!isEmpty(head1))
            {
            System.out.print(head1.data + " ");
            head1 = head1.nextlink;
            }
        System.out.println();
            }

    void reverse()
    {
        boolean flag=true;
        revhead = head;
        link previous=revhead,temp=null,temp2=null;int i=1;
        while(true)
    {
     i++;
        
    for(int j=0;j<(2*rev-1);j++)
    {
        if(isEmpty(previous))
        {
     // 	previous=temp2;
        	break;
        }
        temp2=previous;
        previous=previous.nextlink;
        
    }
        
            for(int k=0;k<rev;k++)
            {
       if(isEmpty(revhead))
        {
            return;
        }
             
        		temp = revhead.nextlink;
                revhead.nextlink = previous;
                previous = revhead;
                revhead = temp;
            }
            
        if(flag){
            head=previous;
        flag=false;
        }
         previous=temp;
        }
       
    }
    }

class RevKLinkedList {

    public static void main(String[] args) {
        
        
    	List list1 = new List();
        
        list1.insert(10);
        list1.insert(20);
        list1.insert(30);
        list1.insert(40);
        list1.insert(50);
        list1.insert(60);
        list1.insert(70);
        list1.insert(80);
        list1.insert(90);
        list1.insert(100);
        list1.insert(110);
        list1.insert(120);
        list1.printlist();
        list1.reverse();
        list1.printlist();
        }
}

a tree is either:
- a branch with a list of child trees
- or a leaf with a value

@
      /  |  \
     /   |    \
    @  D  @
   /   |  \      |
   |    |   |     |
  A  B C   E

1) write a struct to represent it.
2) write a function f() to print out leaf values in in-order travesal

class InvalidTree {
};

template <class T>
struct tree {
    vector<tree> child;
    T*    value;
   
    // no empty tree is allowed 
    tree(vector<tree>& _tree, T* _t) {
        if( !_t && _tree.empty() )
            throw InvalidTree();
    }
    
    bool IsLeaf() const { return branch.empty(); }
    T* GetValue() const { return value; }

    const vector<tree>& GetChild() const { return child; }
};

template <class T>
void f(tree<T>* root) {
    if(root->IsLeaf() ) {
        cout << root->GetValue();
        return;
     }
     
     vector<tree> childs = root->GetChild();
     for(vector<tree>::const_iterator iter = childs.begin(); iter != childs.end(); ++iter) {
         f(iter);
     }
}

Q1: Reverse a linked list without using recursion.
1->2->3->4->5->6
should become
6->5->4->3->2->1

Q2: Then reverse every K elements of a linked list.
1->2->3->4->5->6
should become
3->2->1->6->5->4
for k=3

Ans1: I used this method, but when i try and run this back home, I am not able to print the reverse of the linked list even though the function looks good.
It goes on to print the linked list in the same way as it did earlier. (Now Solved)

Can someone help me understand what is wrong here.
//Figured out the error, look at the correction in comments below//

Ans 2: Working on it (Not Solved)

//Reverse a linked list without recursion.
class link
{
	int data;
	public link nextlink;
	
	link(int d1)
	{
		data = d1;
	}
}

class List{
	
	link head;
	link revhead;
	List(){
	head = null;
	}
	
	boolean isEmpty(link head)
	{
		return head==null;
	}
	
	void insert(int d1)
	{
		link templink = new link(d1);
		templink.nextlink = head;
		head = templink;
	}
	
	void printlist(){
		link head1 = head;
		while(!isEmpty(head1))
			{
			System.out.print(head1.data + " ");
			head1 = head1.nextlink;
			}
		System.out.println();
			}
	
	void reverse()
	{
		link previous=null,temp=null;
		while(isEmpty(head))
		{
			temp = head.nextlink;
			head.nextlink = previous;
			previous = head;
			head = temp;
		}
	
		}

}



public class LinkedList {

	public static void main(String[] args) {
		
		List list1 = new List();
		
		list1.insert(10);
		list1.insert(20);
		list1.insert(30);
		list1.insert(40);
		list1.insert(50);
		list1.printlist();
		list1.reverse();
		list1.printlist();
		}

}

We are given a binary search tree; we need to find out its border.

So, if the binary tree is

10
       /         \
     50           150
    /  \            /    \
  25    75     200    20
 / \           /            / \
15 35    120      155 250

It should print out 50 25 15 35 120 155 250 20 150 10.

If the binary tree is

10
           /         \
         50           150
        /    \         /
      25     75     200
     / \       / \
    15 35  65 30

It should be like 50 25 15 35 65 30 200 150 10.

How can this be done? ?

implement shared_ptr in C++

template <class T>
class shared_ptr
{
private:
	T* _t;
	int *count;
	
public:
	shared_ptr(T* t){
		_t = t;
		count = new int(1);
	}
	
	template <class D>
	shared_ptr(shared_ptr<D>& d){
		_t = d.Get();
		count = d.GetCount();
		*count = (*count)+1;
	}

	~shared_ptr() {
		*count = (*count)-1;

		if(*count == 0)
			delete _t;
	}

	template <class D>
	shared_ptr<T>& operator= (shared_ptr<D>& d) {
		if( this->Get() != d.Get() )
		{
			*count = (*count)-1;
			if( *count == 0)
				delete _t;

			_t = d.Get();
			count = d.GetCount();
			*count = *count + 1;
		}

		return *this;
	}
	
	T* Get() { return _t; }

	int* GetCount() { return count; }
};

remove spaces when they occur more than one time consecutively in string.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define SPACE ' '
 
main()
{
   char string[100], *blank, *start;
   int length, c = 0, d = 0;
 
   printf("Enter a string\n");
   gets(string);
 
   length = strlen(string);
 
   blank = string;
 
   start = (char*)malloc(length+1);
 
   if ( start == NULL )
      exit(EXIT_FAILURE);
 
   while(*(blank+c))
   {
      if ( *(blank+c) == SPACE && *(blank+c+1) == SPACE )
      {}
      else
      {
         *(start+d) = *(blank+c);
	 d++;
      }
      c++;
   }
   *(start+d)='\0';
 
   printf("%s\n", start);
 
   free(start);     
 
   return 0;

#include <cstdlib>
#include <iostream>

using namespace std;


class Empty
{};
 
class Derived1 : public Empty
{};
 
class Derived2 : virtual public Empty
{};
 
class Derived3 : public Empty
{
    char c;
};
 
class Derived4 : virtual public Empty
{
    char c;
};
 
class Dummy
{
    char c;
};
 

int main(int argc, char *argv[])
{
    cout << "sizeof(Empty) " << sizeof(Empty) << endl;
    cout << "sizeof(Derived1) " << sizeof(Derived1) << endl;
    cout << "sizeof(Derived2) " << sizeof(Derived2) << endl;
    cout << "sizeof(Derived3) " << sizeof(Derived3) << endl;
    cout << "sizeof(Derived4) " << sizeof(Derived4) << endl;
    cout << "sizeof(Dummy) " << sizeof(Dummy) << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

and the out put is (In Dev c++)
sizeof(Empty) 1
sizeof(Derived1) 1
sizeof(Derived2) 4
sizeof(Derived3) 1
sizeof(Derived4) 8
sizeof(Dummy) 1

why the size of derived2 is 4 and the size of derived 4 is 8.

- (void)setFinishedSelectedImage:(UIImage *)selectedImage withFinishedUnselectedImage:(UIImage *)unselectedImage

How would you automate testing for this method?

//
//  UIAccelerometer.h
//  UIKit
//
//  Copyright (c) 2007-2011, Apple Inc. All rights reserved.
//
#import <Foundation/Foundation.h>
#import <UIKit/UIKitDefines.h>
/* UIAcceleration and UIAccelerometer are deprecated as of iOS 5.0. These classes have been replaced by the Core Motion framework. These classes will be marked with formal deprecation attributes in a future release of iOS.
 */
typedef double UIAccelerationValue;
@protocol UIAccelerometerDelegate;
UIKIT_CLASS_AVAILABLE(2_0)
@interface UIAcceleration : NSObject {
  @private
    NSTimeInterval timestamp;
    UIAccelerationValue x, y, z;
}
@property(nonatomic,readonly) NSTimeInterval timestamp;
@property(nonatomic,readonly) UIAccelerationValue x;
@property(nonatomic,readonly) UIAccelerationValue y;
@property(nonatomic,readonly) UIAccelerationValue z;
@end
UIKIT_CLASS_AVAILABLE(2_0)
@interface UIAccelerometer : NSObject {
  @private
    NSTimeInterval               _updateInterval;
    id <UIAccelerometerDelegate> _delegate;
    struct {
        unsigned int delegateDidAccelerate:1;
        unsigned int reserved:31;
    } _accelerometerFlags;
}
+ (UIAccelerometer *)sharedAccelerometer;
@property(nonatomic) NSTimeInterval updateInterval; //May be capped at a minimum interval
@property(nonatomic,assign) id<UIAccelerometerDelegate> delegate;

@end
@protocol UIAccelerometerDelegate<NSObject>
@optional
- (void)accelerometer:(UIAccelerometer *)accelerometer didAccelerate:(UIAcceleration *)acceleration __OSX_AVAILABLE_BUT_DEPRECATED(__MAC_NA,__MAC_NA,__IPHONE_2_0,__IPHONE_5_0);
@end

If you were given this header file, how would you test this?

Given a binary tree and 2 values. Write a function to find the 1st common ancestor in the binary tree.

The method I have used is that the common ancestor is the one who would have value between the given 2 values. So for example if the values are 3 and 10. so the common ancestor would be a node with value greater than 3 and less than 10.

here is my code.

public Node getCommonAncestor(Node root,int a, int b)
{
     if((root.value>a && root.value<b) || (root.value<a&&root.value>b))
   {
     if(checkvalue(root,a) && checkvalue(root,b))
     {
         return root;
      }
     else
      {
        return null;
        }
   }
  else if(root.value>a && root.value>b)
   {
        if(root.left != null)
         {
             return getCommonAncestor(root.left,a,b)
         }
         else
         {
            return null;
           }
    }
   else
   {
   
        if(root.right != null)
         {
             return getCommonAncestor(root.right,a,b)
         }
         else
         {
            return null;
           }
    }
}
public boolean checkvalue(Node root,int a)
{
    if(check.value == a)
   {
     return true;
   }
   else if(check.value>a)
    {
       if(check.left != null)
      {
         return checkvalue(check.left,a)
       }
      else
      {
          return false;
       }
     }
     else
     {
          if(check.right != null)
      {
         return checkvalue(check.right,a)
       }
      else
      {
          return false;
       }
      }
}
class Node
{
    int value;
    Node left;
    Node right;
}

Can you suggest whether I am right or not?

Predict the out put of the following code

#include<stdio.h>

int g = 0;

int Add(int i)
{ 
      static int s=0;
      s =s+i;
      g=g+i;
      return s;
}

int main()
{
     int s=0;int g=0,j;
     for(int i=1;i<=11;i++)
     {       g=0;s=0;  
             j = add(i);
      }
      printf("%d,%d",j,g);

return 0;
}

Predict the output

There's a major problem in the implementation of the following class. Can you spot it? How can you fix
the problem? You can propose more than one solution, depending on the requirement specifications of
the class.

#include<iostream>
using namespace std;
template <class T>                            
class Array                                  
{                                              
private:                                        
    T *m_pData;                                   
    unsigned int m_nSize;                         
                                                
public:                                         
  Array(unsigned int nSize) : m_nSize(nSize)      
  {                                           
    if(m_nSize > 0)
     m_pData = new T[m_nSize];                
  }                                           
                                                
  virtual ~Array()                                
  {                    
    if(m_pData != NULL)                           
     delete [] m_pData;                          
  }
                                            
bool Set(unsigned int nPos, const T& Value)
{
  if(nPos < m_nSize)
  {
  	m_pData[nPos] = Value;
  	return true;
  }
  else
  {
  	return false;
  }
}
  
T Get(unsigned int nPos)
{
        if(nPos < m_nSize)
             return m_pData[nPos]; 
        else     
            return T();
}
};

int rows=20000;
int col=30000;
void func1()
{
    for(i=0;i<rows;i++) {
        for(j=0;j<col;j++)
           print(a[i][j]);
    }
}

void func2()
{
    for(j=0;j<columns;j++) {
        for(i=0;i<rows;i++)
           print(a[i][j]);
    }
}

which function is more efficient ?

Given the following code snippet:

void InsertNode(tNode** node, int i){
    if(*node == NULL){
        *node = new tNode;
        (*node)->pLeft = NULL;
        (*node)->data = i;
        (*node)->pRight = NULL;
        SetRootNode(node);
        return;
    }
    else{
        if(i < (*node)->data)
            InsertNode(&((*node)->pLeft), i);
        if(i > (*node)->data)
            InsertNode(&((*node)->pRight), i);
        return;

    }
}
void Func(tNode **node){
    if(*node!=NULL){
        Func(&(*node)->pLeft);
        tNode *temp;
        temp = (*node)->pLeft;
        (*node)->pLeft= (*node)->pRight;
        (*node)->pRight = temp;
        Func(&(*node)->pRight);
    }
}
void traverse(tNode** nd){
    if(*nd!=NULL){
        traverse(&((*nd)->pLeft));
        traverse(&((*nd)->pRight));
        std::cout<<(*nd)->data<<std::endl;
    }
}

Let the input given be
98,15,100,10,78,120,5,12,96,110

What would be the output of the following code snippet?

int main(void)
{
    tree *bT = new tree;
    int i = 10;
    int data;
    while(i--){
        std::cout<<"Enter the node"<<std::endl;
        std::cin>>data;
        bT->InsertNode(bT->GetRootNode(), data);
    }
bT->InsertNode(bT->GetRootNode(), 97);
    bT->Func(bT->GetRootNode());
    bT->InsertNode(bT->GetRootNode(), 99);
    bT->traverse(bT->GetRootNode());
}

Options

-98,15,78,96,97,99,10,12,5,100,120,110

-110,120,100,5,12,10,99,97,96,78,15,98

-100,110,120,98,5,10,12,15,78,96,97,99

-None of these

Given the following code snippet:

void InsertNode(tNode** 
node, int i){

    if(*node == NULL){
        *node = new tNode;
        (*node)->pLeft = 
NULL;
        (*node)->data = i;
        (*node)->pRight = 
NULL;
        SetRootNode(node);
        return;
    }
    else{
        if(i < (*node)-
>data)
            InsertNode(&((*n
ode)->pLeft), i);
        if(i > (*node)-
>data)
            InsertNode(&((*n
ode)->pRight), i);
        return;
    }
}
void Func(tNode **node){
    if(*node!=NULL){
        Func(&(*node)-
>pLeft);
        tNode *temp;
        temp = (*node)-
>pLeft;
        (*node)->pLeft= 
(*node)->pRight;
        (*node)->pRight = 
temp;
        Func(&(*node)-
>pRight);
    }
}
void traverse(tNode** nd){
    if(*nd!=NULL){
        traverse(&((*nd)-
>pLeft));
        traverse(&((*nd)-
>pRight));
        std::cout<<(*nd)-
>data<<std::endl;
    }
}

Let the input given be
98,15,100,10,78,120,5,12,96,110

What would be the output of the
following code snippet?

int main(void)
{
    tree *bT = new tree;
    int i = 10;
    int data;
    while(i--){
        std::cout<<"Enter 
the node"<<std::endl;
        std::cin>>data;
        bT->InsertNode(bT-
>GetRootNode(), data);
    }
    bT->Func(bT-
>GetRootNode());
    bT->InsertNode(bT-
>GetRootNode(), 99);
    bT->traverse(bT-
>GetRootNode());
}

Options

-100,110,120,98,5,10,12,15,78
,96,99

-99,96,78,15,12,10,5,98,120,1
10,100

-110,120,100,5,12,10,99,96,78
,15,98

-98,15,78,96,99,10,12,5,100,1
20,110

Given the following code snippet:

void InsertNode(tNode** node, int i){
    if(*node == NULL){
        *node = new tNode;
        (*node)->pLeft = NULL;
        (*node)->data = i;
        (*node)->pRight = NULL;
        SetRootNode(node);
        return;
    }
    else{
        if(i < (*node)->data)
            InsertNode(&((*node)->pLeft), i);
        if(i > (*node)->data)
            InsertNode(&((*node)->pRight), i);
        return;
    }
}
void Func(tNode **node){
    if(*node!=NULL){
        Func(&(*node)->pLeft);
        tNode *temp;
        temp = (*node)->pLeft;
        (*node)->pLeft= (*node)->pRight;
        (*node)->pRight = temp;
        Func(&(*node)->pRight);
    }
}
void traverse(tNode** nd){
    if(*nd!=NULL){
        traverse(&((*nd)->pLeft));
        traverse(&((*nd)->pRight));
        std::cout<<(*nd)->data<<std::endl;
    }
}

Let the input given be
98,15,100,10,78,120,5,12,96,110

What would be the output of the following code snippet?

int main(void)
{
    tree *bT = new tree;
    int i = 10;
    int data;
    while(i--){
        std::cout<<"Enter the node"<<std::endl;
        std::cin>>data;
        bT->InsertNode(bT->GetRootNode(), data);
    }
    bT->InsertNode(bT->GetRootNode(), 99);
    bT->traverse(bT->GetRootNode());
}

options

-110,5,12,96,78,15,99,110,120,
100,98

-5,10,12,15,78,96,98,99,100,11
0,120

-120,110,100,99,98,96,78,15,1
2,10,5

-98,100,120,110,99,15,78,96,1
2,5,110

Suppose you have the following code:

void InsertNode(tNode** node, int i){
   if(*node == NULL){
      *node = new tNode;
      (*node)->pLeft = NULL;
      (*node)->data = i;
      (*node)->pRight = NULL;
      SetRootNode(node);
      return;
   } else {
      if(i < (*node)->data)
         InsertNode(&((*node)->pLeft), i);
         if(i > (*node)->data)
            InsertNode(&((*node)->pRight), i);
         return;
   }
}

void Func(tNode **node){
   if(*node!=NULL){
      Func(&(*node)->pLeft);
      tNode *temp;
      temp = (*node)->pLeft;
      (*node)->pLeft= (*node)->pRight;
      (*node)->pRight = temp;
      Func(&(*node)->pRight);
   }
}

void traverse(tNode** nd){
   if(*nd!=NULL){
      traverse(&((*nd)->pLeft));
      traverse(&((*nd)->pRight));
      std::cout<<(*nd)->data<<std::endl;
   }
}

Let the input given be
98,15,100,10,78,120,5,12,96,110

What would be the output of the following code snippet?

int main(void) {
   tree *bT = new tree;
   int i = 10;
   int data;
   while(i--){
      std::cout<<"Enter the node"<<std::endl;
      std::cin>>data;
      bT->InsertNode(bT->GetRootNode(), data);
   }
   bT->Func(bT->GetRootNode());
   bT->InsertNode(bT->GetRootNode(), 99);
   bT->Func(bT->GetRootNode());
   bT->traverse(bT->GetRootNode());
}

Options

-5,10,12,15,78,96,98,99,100,1
10,120

-5,12,10,99,96,78,15,110,120,
100,98

-5,10,12,15,78,96,99,98,100,1
10,120

-98,100,120,110,15,78,96,99,1
0,12,5

Fill in the blanks:

--   --  --  H  I   K  L   M   N  T
     --   --  --  G  J  O  P  Q   R  S

For those who get bored of sorting/hashing/string manipulation problems, here is the geometric one:

Given n lines in the plane (for simplicity assume no
3 lines intersect at one point). 
Count the total number of triangles in the plane created by these lines. 
Observe that smaller triangles may be part of larger ones.

Look here for example:
h t t p://farm8.staticflickr.com/7021/6465828833_15e7447992_z.jpg

Given an array and a number K. You have to 
find out longest subset from the array whose 
all pair sum will be greater than k.
ex: {8,3,4,1,6,2,5,7,9} and K=12
ans: {8,6,7,9} or {5,7,8,9}

A binary tree is given we need to print vertical sums of nodes. for example

1    2      3        4     5

  |      |       5        |     |
  |      |     / |       \ |     |
  |      |   /   |        8     |
  |      | /     |       / |    \|
  |      4      |    /    |   10
  |    / |  \    9        |     |
  |  /   |      \          |     |
  7     |      6               |
  |      |      |          |     |
  |      |      |          |     |
  -----------------------------------------------
  7     4     20       8   10

Here we need to print sum 7,4,20,8,10.

how to correctly instantiate this class:

template < template < template < class > class, class > class Param >
struct Bogus {

    int foo() {
        printf("ok\n");;
    }
};

#include<stdio.h>
int main() {
int i,j;
j = 10;
i = 3;
//i = j++ - j++;
//i = i++ + ++i;
//i = j++ - j++ + i++ + ++i;
printf("%d\n", i);
}

If I un-comment the first comment then output = 0
if second then output = 9
if third then output = 8

Please explain why this is so

Write a poker function which will take an array of 5 ints and will return true if 2 elements and 3 elements are equal

for ex . 10 5 10 5 5 returns true
         5 10 10 10 5 returns true 
         1 5 10 10 10 returns false 
         1 2 3 4 5 returns false

What is wrong with following code?

#include<cstdio>
using namespace std;

class Lock {
public:
	Lock():isLooked(false) { }
	bool AcquireLock() { return isLooked ? false : (isLooked=true);}
	void ReleaseLock() {isLooked = false; }
private:
	bool isLooked;
};

template <typename T> 
class Singleton {
private:
	static Lock lock;
	static T* object;
protected:
	Singleton() { };
public:
	static T * Instance();
};

template <typename T>
T * Singleton<T>::Instance(){
	if (object == 0) {
		if(lock.AcquireLock()){
			object = new T;
			lock.ReleaseLock();
		}
	}
	return object;
}


int main() {
	int* singleton_foo = Singleton<int>::Instance();
	return 0;
}

result of this:

main()
{
  fork();
  fork();
  fork();

    printf("hello\n");
}

char ch1 = 0,ch2 = 0;
try { ch1 = (char) System.in.read(); }
catch(Exception e) {}
switch(ch1) {
   case 'a': 
      ch2 = '1';
   case 'b':
      ch2 = '2';
   case 'c':
      ch2 = '3';
   default:
      ch2 = '4';
}

In reference to the above, if during execution the user presses "b," what is the ending value of "ch2"?

std::string bytesToHex(char * bytes, size_t size)
{
    std::string result;
    for (int i=0; i<size; i++) {
        char hexByte[2];
        sprintf(hexByte, "%02x", bytes[i]);
        result.append(hexByte);
    }
    return result;
}

what does this fn do?
Is there any problem with the code?
how do you fix it?

Write a program to find out the sum of nodes which does not have siblings in a binary tree

I have written following logic and he was impressed with the logic, I think I did well but could not able write the logic for the traversing as I was not prepared but he said explain what is want to do and I explained, hoping for good results.

public int returnNodeValue(Node t)
{
    BOOL thereIsNoLeft = false;
    BOOL thereIsNoRight = false;
    int returnValue = 0;
    

    if(t.left != null)
    {
      thereIsNoLeft = true;   
       returnValue = t.left.value;
    }
    
    if(t.right != null)    
    {
         thereisNoRight = true;
         returnValue = r.right.value;
    }
    
    if(!(thereIsNoLeft && thereisRight))
    {
     return returnValue;
    }
    return 0;
}

(3rd phone interview)functions to print first n odd powers of 3, where n is given to the function:

void power(int n)
{
  if(n<=0)
    throw IllegalArgumentexception
  else
   {
     for(i=1;i<n;i++)
     int result = Math.pow(3, 2i-1);
     System.out.println(result);
   }
}

Given a set, write a code to create a power set.
Eg: Set = {1,2}
Power Set - List containing sets {1},{1,2}, {2}, { }

A sample programme:

package misc;


public class PowerSet {
	
	
	private void printPowerSet(String inputString, String prefixString, int startIndex){
		if(inputString == null){
			return;
		}
		for(int i=startIndex;i<inputString.length(); i++){
			String str = "";
			str = prefixString +  inputString.charAt(i);
			System.out.println("{" + str + "}\n");
			printPowerSet(inputString, str, i+1);	
		}
		
	}
	
	
	
	
	public static void main(String args[]){
		String inputStr ="123";
		System.out.println("{ }\n");
		for(int i=0; i<inputStr.length(); i++){
			PowerSet powerSet = new PowerSet();
			
			System.out.println("{" + inputStr.charAt(i) + "}\n");
			powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);
			
		}
	}

}

Given a binary tree.
It might be full or some nodes might be missing.
Every node has a extra "next" pointer.
Make the "next" pointer point to the next cousin/sibling node. Last node's "next" pointer should point to null.

Eg.

Given Binary Tree -
              1
       2             3
    4     5      6      7
  8  9  10   12 13  14  15

1's next = null

2's next = 3
3's next = null

4's next = 5
5's next = 6
6's next = 7
7's next = null

8's next = 9
9's next = 10
10's next = 12
12's next = 13
13's next = 14
14's next = 15
15's next = null

Generate nested () based on the input given.

ie. if n = 3 
O/p
((()))
()()()
(())()
()(())
(()())

My solution is as follows

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void printPar(int l,int r,string s)
{
    if(l > 3 || r > 3 || r >l)
        return;



    if(l==3 && r==3)
    {
        cout<<s<<endl;
        return;
    }
    else
    {

         if((l<3))
         {
            s+="<";
            l = l+1;
            printPar(l,r,s);
         }
          if(r<3 && r < l)
         {
             s+=">";
             r = r+1;
            printPar(l,r,s);
         }
       //  cout<<"Exiting "<<l<<" & "<<r<<" "<<s<<endl;
    }
}




int main()
{
    string s;
    printPar(0,0,s);
    return 0;
}




Output :
<<<>>>
<<<>>>
<<><>>
<<><>>
<><<>>
<><<>>
<><><>
<><><>

This one is straight out of the book , the code given in book is wrong. Can any one help in correcting my logic.

understand why there are duplicate values in the list. i.e once the function is called using recursion and ends up following the next branch on execution. The second print is due to the function it self falling on the second branch. Is there any way to handle this ? I really do not want to go the global-set route.

Also , in my head this code should print (())() - Yet it does not :(

Can some one please point out the error ?

In the CrackingTheCodeInterview book solution, CareerCupLibrary - TreeNode, the isBST method is like this:

public boolean isBST() {
		if (left != null) {
			if (data < left.data || !left.isBST()) {
				return false;
			}
		}
		
		if (right != null) {
			if (data >= right.data || !right.isBST()) {
				return false;
			}
		}		
		
		return true;
	}

But I think this method only checks whether the tree is searchable, it can NOT check whether the tree is balanced. Am I right folks?

Count the number of binary 1's in an integer.

My Ans:

//assume 32 bit number
int num = given number;
int count =0;
if (num%2 != 0) count++;
for (int i=0;i<32;i++)
{ if((num = num>>1)%2 !=0)
   count++;
}
print count;

What is wrong with this piece of code.

int main()
{
	for(;;)
	{
		short n;
		scanf("%d",&n);
		if( n == 42)
			break;
	}
	system("pause");
	return 0;
}

<round 1 >

6) what is fork()

sub questions

1) How many times "SIVA" will be printed

i = 0 ;
while (i < n )
{
    fork();
    printf("\n SIVA");
    i++;
}

2)How many times "SIVA" will be printed

i = 0 ;
while (i < n )
{
    printf("\n SIVA");
    fork();
    i++;
}

4) How to initialize Constant variables in class( or object).

example 1: throws error "uninitialized member 'myclass::i' with 'const' type 'const int'
"

#include <iostream>
using namespace std;

class myclass{
public:
       const int i;

       myclass()
       {
            i = 10;  // here throws error
       }
};

int main()
{
      myclass m;
      cout<<m.i<<endl;
      return 0;
}

example 2: below piece of code works fine .

#include <iostream>
using namespace std;

class myclass{
public:
       const int i;

       myclass() : i(10)
       {

       }
};

int main()
{

      myclass m;
      cout<<m.i<<endl;
      return 0;
}

Can some one please explain me , why second example works fine ? . why not first example ?

<round3> ( Manager round )
7. Check given tree is symmetric or not ?

e.g

1) Symmetric
      1
     / \
    2   2
   /     \
  3       3
2) non-symmetric
      1
     / \
     2  3

Implement an algorithm to print out all files below a given root node.

package file;

import java.io.File;

public class PrintFile {
	
	private void printFile(File file){
		File[] childFilesList = file.listFiles();
		if(childFilesList !=null && childFilesList.length>0){
			for(File childFile : childFilesList){
				if(childFile.isDirectory()){
					printFile(childFile);
				}
				else{
					System.out.println(childFile.getName());
				}
			}
		}
		
	}
	
	public static void main(String args[]){
		PrintFile printFile = new PrintFile();
		printFile.printFile(new File("C:\\Shared"));
	}

}

Write an 0(n) algorithm for detecting conflicts in appointments.

public class Appointment {
long startTime;
long endTime;
boolean hasConflict;
}

public static ArrayList<Appointment> markCOnficts(ArrayList<Appointment> apntmnts)

//your code here..for each appointment if it 
//has a conflict you need to set hasConflict 
//parm = true

find a bug in following code :

class A
{
public:
    static int i;
    void print()
    {
         cout<< i << endl ;
    }
};

int main()
{
 A a;
 a.print();
}

I run above code, and I am getting "ndefined reference to `A::i'" . Why I am getting this error ?

Round 2 :
Write a code to print level order traversal of N-ary tree

data structure can be assumed as 
class Node{
     vector<Node> children;
     int val;  
}

Round 1 :
suppose you are given a function void NumberofSum(int n) , write a code such that will print all the numbers that will sum up to n

For Ex.
n           output
1        {1}
2        {(1,1) , (2)}
3        {(1,1,1), (1,2) , (3)}
4        {(1,1,1,1),(1,1,2),(1,3),(2,2) , (4)}

Question on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes ?

Tree node contains 3 pointers *left, *right and *Successor .

Struct node{
         int data;
         struct node *left;
         struct node *right;
         struct node *successor; 
    };

INORDER Traversal: **DBEAFCG**
**Note:** A inorder successors are F,C and G.

**Function prototype:** void FillSuccessorNodes( struct node *root);
Tree's root node given to us and we need to fill successor pointer for all nodes.

case 1) some of the Successor pointers may be **NULL** . This case you have to fill that pointer with immediate Inorder Successor.

Example: if A->Successor == NULL, then fill A->Successor = F

case 2) some of the Successor pointers may already  points to correct successors. This case You no need to modify successor pointers.

Example: 1) A->successor = F is valid

2) A->successor = C is valid

3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.

case 3) Some of the successor pointers are **not NULL** but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.

Example:

1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.

2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F.

**1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed.
2) she gave some hint i.e we can use HASHing.**

**If you know the solution for this problem, please let me know .**

Why does the following code throw segmentation fault?

int main(){
	int myArray[10] = { 1, 2 };
	delete[] myArray;
}

you are given n files with m entries in each line separated.

for example file1 has a\n b\n c\n d(where \n is new line character) 
similarly file2 has a1\n b1\n c1\n d1\n
and file3 has a2\n b2\n c2\n d2\n
your job is to print total 4^3 combinations.
Its not mere permutation problem.
the output is like
a a1 a2 \n
a a1 b2 \n
a a1 c2 \n
a a1 d2 \n
a b1 a2 \n and so on. i.e total combination of file2 and file3 with a
....
....
....
....
b a1 a2 \n
b a1 b2 \n
b a1 c2 \n
......and so on toal combination of file2 and file3 contents with b

......
....
similarily for c (16 lines)
and similarly for d (16 lines)

Hence total of 4^3 64 lines...

Note:- you have to do it by recursion.
there can be m files and n entries in each...
so don't hardcode for 3 files.

How do you find the depth of the minimum depth node in a binary tree?
In the tree below the minimum depth is 3 (of node 22).

20
      /    \
     5      25
      \     /  \
       7   22  30
       / \      \
      6   8      33
                  \
                   35

Write an algorithm to convert string "1234.56" to its float equivalent.
Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MSIntervewPreparation
{
    class ConvertStringToFloat
    {
        static void Main(string[] args)
        {
            string str = "1234.56";
            float num = 0.0F;
            float multiplier = 0.1F;
            bool isDecimalReached = false;
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == '.')
                {
                    isDecimalReached = true;
                    continue;
                }
                if (!isDecimalReached)
                {
                    num = (num * 10) + (str[i] - '0');
                }
                else
                {
                    num += (str[i] - '0') * multiplier;
                    multiplier *= 0.1F;
                }
            }
            Console.WriteLine("Input String: " + str);
            Console.WriteLine("Float Number: {0} ", num);
        }
    }
}

Write a function to convert "1234.56" into its float equivalent.
Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MSIntervewPreparation
{
    class ConvertStringToFloat
    {
        static void Main1(string[] args)
        {
            string str = "1234.56";
            float num = 0.0F;
            float multiplier = 0.1F;
            bool isDecimalReached = false;
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == '.')
                {
                    isDecimalReached = true;
                    continue;
                }
                if (!isDecimalReached)
                {
                    num = (num * 10) + (str[i] - '0');
                }
                else
                {
                    num += (str[i] - '0') * multiplier;
                    multiplier *= 0.1F;
                }
            }
            Console.WriteLine("Input String: " + str);
            Console.WriteLine("Float Number: {0} ", num);
        }
    }
}

void func( int *p)
{
  // Add code to print MEMORY SIZE which is pointed by pointer P.
}
int main()
{
  int *p = (int *) malloc (10);
  f(p);
}

How can we find MEMORY SIZE from memory pointer P in func() ?

int main()
{
	int i = 32242;
	int k = find(i);
	return k;
}

int find (int j)
{
	if (j > 0)
	{
	j = j%10 + find(j/10);
	printf(" %d ", j);
	}
	return j;
}

Find the output of the program?

Ans: 3 5 7 11 13

int x = -20;
unsigned int y = 6;
z = x + y;

what is the value of z?

char *xyz()
{
   char str[32];
   strcpy(str,"Hello there!");
   return(str);
}

void main()
{
  printf("%s",xyz());
}

What is the output?

int a[] = { 1, 2, 3, 4, 5 };
const int N = sizeof(a)/sizeof(a[0]);
for (int i = 0; i < N; ++i)
   std::cout << (i[a-i]%N)[a+i-1] << " ";

int CutNPaste(char* str, int start, int stop, int destination)

Round-2-Qn-1) Given a linked list L, we need to make a clone L'.
Note: a) Each node in the given list has an additional link called random that can point to any node (can also be null)
b) we need to make a clone of the list without using any additional space (need to allocate memory only for new nodes 1', 2', 3',...)
c) complexity should be O(n)

-->------
            |       |
L = 1-->2-->3-->4-->NULL
    |   |   ^   |
    |___|___|   |
    |   |___|   |        
    |<-----------

1->next = 2      1->random = 3
2->next = 3      2->random = 3
3->next = 4      3->random = NULL
4->next = NULL   4->random = 1

In L', the nodes should be
1'->next = 2'      1'->random = 3'
2'->next = 3'      2'->random = 3'
3'->next = 4'      3'->random = NULL
4'->next = NULL   4'->random = 1'

Round-1-Qn-2) Given a binary tree, we need to create a matrix.

Example:

A
    / \
  B     C
 / \   / \
D   E F   G

 |A|B|C|D|E|F|G|
------------------
A|
B|1               (B is child of A)
C|1               (C is child of A)
D|1 1             (D is child of A & B)
E|1 1             (E is child of A & B)
F|1   1           (F is child of A & C)
G|1   1           (G is child of A & C)

Round-1-Qn-1) Find vertical sum of given binary tree.

Example:

1
    / \
  2     3
 / \   / \
4   5 6   7

The tree has 5 vertical lines

Vertical-1: nodes-4     => vertical sum is 4       
Vertical-2: nodes-2     => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3     => vertical sum is 3
Vertical-5: nodes-7     => vertical sum is 7

We need to output: 4 2 12 3 7

Given a Hash -

my %hash = (
                ABC => [123,456,789],
                PQR => 345,
                XYZ => 567,
                LMN => {
                                abc => 0,
                                pqr => 1,
                                lmn => 2,
                                xyz => {
                                                A => 0,
                                                B => 1,
                                                c => [ {1 => 'ONE', 2 => 'TWO',},
                                                       {ONE => 1, TWO => 2,},
                                                       {Number => 'Decimals'},
                                                       {Words => 'Alphas'},
                                                       'Sample'
                                                ]
                                        }
                        },
                OPQ => 'WORD'



);

Write a generic function to find value of key input by user.

e.g. In above example if key input by user is 'Words' then value found by search function should be 'Alphas'

Write Search($hashRef,$key) function where, hash could be of any type/level such as -
Hash of Hash of Hash of Hash
Hash of Array of Hash.
etc. etc.

Given a Hash -

my %hash = (
                ABC => [123,456,789],
                PQR => 345,
                XYZ => 567,
                LMN => {
                                abc => 0,
                                pqr => 1,
                                lmn => 2,
                                xyz => {
                                                A => 0,
                                                B => 1,
                                                c => [ {1 => 'ONE', 2 => 'TWO',},
                                                       {ONE => 1, TWO => 2,},
                                                       {Number => 'Decimals'},
                                                       {Words => 'Alphas'},
                                                       'Abhishek'
                                                ]
                                        }
                        },
                OPQ => 'WORD'

        );

What happens when the method is called? Explain

public int normal(){
		try{
			return 10;
		}finally{
			return 20;
		}
	}

Implement N stacks using 

constant sized array(space). Until the array 
is completely filled, I should be able to push 

elements to any one of the N stacks.(i.e.)Do 
not reserve space for the stacks. And I should 
also be able to pop elements from any stack.

How many constructor (including copy constructor) and destructors will be called for test1 and test2?

#include <iostream>
using namespace std;

class Base{
public:
	Base(){cout << "Base()" << endl;}
	Base(const Base&){cout << "Base(const Base&)" << endl;}
	~Base(){cout << "~Base()" << endl;}
};

Base func(Base b){return b;}

void test(){
	Base a;
	func(a);
}


void test(){
	Base a;
	Base b = func(a);
}

int main(){
	test1();
        test2();
	return 0;
}

class Base{		
		int a;
	public:
		int b;
		Base(){a = 10; b = 11;}
		virtual ~Base(){};
		class Derived;
		friend Derived;
	};
	class Derived: private Base{
	public:
		Derived(){cout<<b<<endl;}
		void p(Base b){cout<<b.a<<endl;};
		virtual ~Derived(){};
	};

int main(){
	Base b;
	Derived d;
	d.p(b);
	return 0;
}

Can this code be compiled and why?

Consider a prog. lang which has only single datatype called 'variable'. A variable x of type 'variable' can hold only +ve values(i.e 0<=x<=infinity).
We have only the following constructs defined in the language:

increment(x)         -----> increments the value of x by 1.
   setzero(x)             ------>  resets the value of x to 0.
   loop(x)                  -------> loops x no of times.

Using the above constructs WAP to find   x!/x.

Note: i) No other operator is allowed.
          ii) u cant define ur own constructs.
         iii) within the loop if the value of x changes then this does not change the value of x which is used to iterate.. for ex:
            if we loop(x)  with x=5
        then there will be five iterations even if the value of x changes inside the loop...

all the best !!

Given the below table:

LEDGER
	ID		VARCHAR(11)		PRI
	Month		VARCHAR(2)
	Year	          VARCHAR(4)
	Amount	REAL

Compose the query that will output the report in the following format:

Year      1980  1981 1982  ...................2009
Jan       $$          $$
Feb
Mar
..	
.
.
.
Oct
Nov
Dec

Where $ if the total Amount for a given Month

The following code is the real code. Try to implement bridge design pattern. Question:
1) Please check if the code has problem?
2) Do you need to delete the ri and sr object? If yes, how?

#include <stdio.h>

class shape_Impl
{
  public:
	  virtual int area()=0;
};


class RectImpl:public shape_Impl
{
    int length;
    int width;

public:
	RectImpl(int l=0, int w=0):length(l), width(w){};
	~RectImpl(){};
	virtual int area() {return length * width;};

};


class shape
{
  public:
     shape(shape_Impl  * imp) { Impl=imp;};
    ~shape() {delete Impl;};

    int area(){return Impl->area();};

  private:
    shape_Impl *Impl;
};



int main()
{
	shape_Impl* ri = new RectImpl(100, 100);
	shape *sr = new shape(ri);
	printf ("area: %d\n\n\n\n\n\n", sr->area());

	
	delete ri;
	delete sr;

	return 0;
}

to print

*
*
**
**
***
***
****
****
*****
*****

#include<stdio.h>
void main()
{
    int n,j,k,l,i;
          printf("enter the number");
            scanf("%d",&n);
            for (i = 1; i <= n; i++)
            {
                for (j = 1; j <= 2; j++)
                {
                    for (l = n; l > i; l--)
                    {
                        printf(" ");
                    }
                    for (k = 1; k <= i; k++)
                    {
                        
                        printf("*");
                       
                    }
                   printf("\n");
                }
            }
			getch();
}

Design testcases for the strcpy function.

// Takes two null terminated strings
// and copies the chars in src onto dest
// including the null character.
strcpy(char *dest, char *src);